I agree with Forever, use a Sandile cos I tried one in Black and she was awesome. I recommend getting Moxie if you can and I can suggest an ideal nature for it, since Sandile is Physical-based attacker I'd say Adamant or Naughty.
Sewaddle has a large pool of weaknesses (including that 4x Fire/Flying, ouch!) so I'd say you should try Deerling when you get to Route 6 it gets a great Attack stat as a Sawsbuck. I use one in Black and she was awesome, I recommend a Jolly nature if you want extra Speed or Adamant for extra Attack.
Or you could get a Ferroseed in Chargestone Cave, they take a long time to train though but its Iron Barbs combined with Rocky Helmet make it a great wall plus only 2 weaknesses to worry about.
It's all about Sawsbuck for offensiveness or Ferrothorn for defensiveness.
For a Water-type, I'd recommend Jellicent (you can catch its pre-evo, Frillish after you get Surf) cos it's bulky and a good Special-based attacker too.
Or try Swanna (Ducklett are found on Driftveil Drawbridge) if you need a Flying-type that also covers your Water-type. It learns some good attacks plus it's fast and it's a good HM slave. You could teach it Fly because most people usually have at least a Flying-type to get somewhere with Fly.
Archeops (evolves from Archen) is also a nice Flying-type cos it's strong and can learn Acrobatics.
Solosis is nice but it is hard to train with such low Speed, I guess you could try Elgyem later on, its stats are similar to Solosis but is slightly faster (they still both have low Speed though). If you plan on using either Solosis or Elgyem, I recommend Modest for a Sp. Atk boost or Naive/Timid for more Speed. And I recommend Solosis with Magic Guard.
Solosis/Duosion/Reuniclus and Elgyem/Beheeyem are both very similar stat-wise but it all depends on which one you want to use.