[Shovah32]

Well:
1)Water provinces are generally fewer and larger than land provinces, moving through 1 water province is generally the same as moving multiple land provinces.
2)Strong battlemages, many common indy archers and the fact that only rlyeh has underwater missile units(if illithids can be counted as missile units) makes up for it. Most people dont have underwater missile units.
3)Everyone else suffers from this, why shouldnt you?
4)This is probably just the people your playing with, i havnt noticed any real problems with this.
5)Or you could build more castles which is what you should be doing. Also most maps have few water provinces so this shouldnt really be an issue.

So basically yes, apart from mind blasting rlyeh having missile troops(EA mind-blasters are aquatic, MA are quite expensive and LA are the same price but you have a death dominion) other nations have these weaknesses.