Pielorinho
Iron Fist of Pelor
If I were you, I'd just figure that the animal companion isn't a major part of the character, and then grab something aquatic. Having a shark companion is too cool to pass up, IMO. Sure, you'll leave it behind when you go ashore -- but when you're in water, you'll have extra fun. And if the campaign shifts to be mostly landbound, you can bid the shark farewell and befriend a goat or something.
Daniel
Daniel