I've always felt that if they added a chance for random encounters while fast traveling to your destination, it would be awesome. As it works now, you can travel from Anvil to Cheydinhal with no chance of anything possibly going wrong, it's actually kind of over powered. How cool would it be though if halfway to Kvatch you were attacked by some bandits or whatever and dropped out of fast travel. Wouldn't even have to be enemies, maybe you run into an Imperial patrol or something. You could even work your idea for a navigation skill into it, high navigation could lower your chance of random encounters.
Sorta like in Dragon Age: Origins?