If you've ever played the Fallout games you encountered this (Fallout 3 had 'em too) and it was an excellent trade-off for the convenience of fast traveling. Of course this would be a rather complex mod...

- When Fast Traveling, assume the character is taking the shortest distance between point A and point B.

- We'd have to be able to figure out where it's "safe" to teleport in one of the cells between point A and point B.

Then teleport your character (carriage too, if being used) into the cell with some enemies (probably Bandits most of the time, but we could even do Dragons). Here's some additional ideas:

- You can pay a decent amount of gold to temporarily hire a scout if you're at any of the cities (they'd hang out near the carriages). The amount needed would be based on your level, and scouting only reduces the chance, not eliminates it.

- The carriage can be changed to a caravan with a random chance of NPCs joining you in the fight.

- You can pay for mercenary protection for a certain number of trips/days, and they'll only appear to help in these random encounters.

- Assuming you always take the "road most traveled", traveling NPCs not hostile to you may randomly join the fight.

- Unique encounters!

- Tied into mods like "Tamriel Travelers" ported over to Skyrim.