You're right, that it is a difficult nut to crack.
From my own experience, I'd advise to start with the map definition. Not specifically the 3D graphics, but an abstract layer that can be used to do pathfinding with. But importantly, make sure this is compatible with the graphics and terrain features you will use, and also able to be modified on the fly.
Because there are two things you'll need to consider when you tackle the pathfinding:
(1) environmental features like cliffs and deep water being an obstruction, and
(2) stationary units / buildings / destructible doodads being an obstruction.
I think it's worth remembering that in all professions, there are people who are geniuses at what they do. Whether it's rocket science, or relativity theory, or writing software...
So I think it's fair to assume that even in computer games, the most cleverly engineered ones we see, do indeed represent the best that the human mind can produce.
Expecting to compete with those, would be...
ambitious.
