There's actually a classic GDC Talk about this very subject!
They talk about using big visible markers (called weenies) for orientation and to help draw players. Having seemingly multiple paths that actually end up in the same destination. Tiny rewards for exploration. Good stuff