Well if you still want to do some travelling to find locations so it does'nt feel like a total cheat as far as possible and get MOD locations at the same time this is what i do when i start a new character:
Akatosh flying mount
Mapmarker mod by Leman
Wayshrine marker mod (if you have KOTN) by Mezlo
Oblivion gate mapmarker remover by Quarn
and fly around from marker to marker.
The advantage of this is that when you look around you get almost all the wayshrine's & gates and if there are any markers, the locations from mods