I've just finished listening to episode 9 of the podcast, and I thought I'd put a few PC games forward.
Homeworld: it's the game that introduced me to naval gaming, and the only RTS I know of with true 3D movement and combat.
Empire-Total War: this is turn-based strategy, real-time tactical. The game starts at 1600 and lets you directly control your naval vessels in real-time combat.
Europa Universalis IV: a highly abstracted real-time grand strategy game, set between the late 1400s and early 1800s with a strong naval aspect.