I agree that too many random encounters is tedious and not fun. I am suggesting more of a sporadic random encounter. Shoot! Even in tabletop, I don't spam random encounters. Their supposed to be for flavor, not a filler.
So, you still have all the encounters you do now, but have like periodic rolls made every couple of minutes of gameplay. Game does the roll without you knowing. Roll d100 or something. On a 1-10, random encounter. So like 10% chance every 5 minutes or something.
Ah I don't know. I just thought that random encounters, when done sporadically, makes the game more surprising; not so... expected.