I would love random encounter to increase the feeling of danger... Especially at resting if you don't rest at camp.
This could become a great feature if Larian rework a bit the actual immersion breaking rest system.
About fast travel I don't really know. I would love that too but what do you think about ?
An instance out of the map in which you fight against several creatures ? (immersion breaking too),
Creatures appearing on the road between 2 fast travel points ? Hard to implement I guess.