Yes, Tripod Fish Pokemon would be awesome. They should definetly do more Pokemon that live on the bottom of the ocean. I love Relicanth, who is based off of the Coelacanth. Seriously, the only difference between the Coelacanth and then Relicanth is the names.
Sandshrew was NOT based off of the Pangolin. I thought it would be obvious that he is based off of a mix between a shrew and a prairie dog.
I love the Sea Slug that sirboulevard posted! That would be a bit like a Lotad. The final evolution could be a giant Coral Reef!!
As for the Fearow/Vulture thing, I wouldn't know. I think Fearow is more like a condor, or in general a large bird.
One more thing, I would love to see a "Torterra of the Sea" by making an archipelago on a Crab's back! I've drawn some awesome pictures of that too! My Idea was having like palm tree's on it's back and stuff.