I agree, it sounds like a lot of fun.
You could stick a bunch of guys at different towns, then when you pick one up, he names another town at random & asks to be taken there. I've got some code to do that bit already, because of my own odd idea that I'll post next (random assaults).
You could scatter a few vehicles at different towns, and then the player could go looking for them, with an expectation that something is parked near (say) Chapoi, but not knowing whether it'll be a M113 or UH-60.