Actually, Water Pulse is the better move. Yes, Brine does 5 more damage, and can even deal double damage in some situations, but the move only has 10 PP. This will be a quite annoying factor in-game, so you are better off with Water Pulse, which does enough damage. Think about it. Would you really sacrifice 10 PP for 5 more damage?
Once you get the chance, however, Surf, Dive, and Waterfall are both better moves, as well as HMs that will help you get through the game without an HM slave.
Hope I helped. :)