Yes, navy footwear can be hard to source, definitely! I no longer worry about that so much -- I'll just wear navy with black, if I want a dark shoe -- but I do keep my eye open for navy options, and then hang onto them for years when I find them.
It's entirely possible to find less traditional or classic navy items (see Bijou's jacket, for instance, and several of her other items) -- but in my experience, it is really hard to find anything with what you might call "edge" or any avant guard items in navy. Whereas if you are after edge, or any avant guard flair, you can easily source it in black.
I find that a frustration, for sure, especially during those phases when I feel like I would like to move my style more in that direction. (This seems to come up for me every few years and then I give up, LOL).
A lot of my own navy forms a sort of "core column" if that makes sense. Simple pieces that create (or could create) a column of colour under a more interesting statement third piece. Or simple separates that can let another piece become the focal point. So it's fine for me if they are relatively classic in cut or style. Still, I often admire the sometimes more interesting black essentials that Jenn or Gryffin (to take just two examples) can source. Sometimes it's easier to find grey items in more interesting cuts. But greys can be tricky as well.