I've had the same experience as you. A while back, I contributed to the "nerfs and buffs" thread in Variants and suggested that Navigator would be better priced at $3. After that, I started experimenting more with it and found it to be a lot more useful than I realized. It's still not strong at $4, I think -- that would be an overcorrection -- but sometimes it sure is nice to have. If you can use it to save yourself from a whole bad hand now and again, which is not uncommon, that can have incalculable ramifications on your game as the benefit compounds in subtle ways as you continue to play.
Beyond cold strategy, it's kind of a fun card to play, too, as it's a somewhat unusual effect. Chancellor, Pearl Diver, Golem, Conspirator, Tribute, and a few others fall into this category for me too. Whether strong or weak, smart or ill-advised, their uniqueness makes the playing of them fun. Which, to me, is more important than the strategy.