I really liked battleship with the twist of different ships you could buy. It's probably not the first to do it, but it's the first I've actually played.
Only thing I wish it had was a sound effect when your own ship gets hit.
