I feel your pain, Makatak. After completing FO1, which was brilliant in just about every aspect, I started FO2 and it made me want to punch myself in the face. After I did my thing at the Den, I decided to go straight to Vault City because it seemed like a logical idea (it's exactly what I would have done in FO1). I mean, I have to get that GECK as soon as possible for my people, right? Well, no. I kept on getting killed in the random encounters before I got even 8 squares away from the Den. So after putting the game down for a few days, I decided to head southeast and my game took on a whole new direction.
Another tip is to use the terrain that is given to you. Run to the trees for cover or use tents to your advantage. It does suck that the game puts you smack dab in the middle of a pretty large square and make you run away from up to 8 thugs who take their sweet time chasing you down (I have a dart board near my PC, so I hone my real-life throwing skills while I wait for my next turn). Even though it can be frustrating, it is fun to really feel like you are running for your life in a wasteland with a bunch of drugged up psychos hot on your tail.
It seems appropriate to bring up another random encounter issue. This one happened to me down by NCR and the two Vaults, just before I got my hands on that GECK. I would constantly encounter "remnants of Master's army" and have to watch those impossibly slow moving red laserballs destroy me time after time. I was a pretty powerful character for that stage of the game, but yet, the game put me in situations where I had zero chance of survival. I do not like to play the game saving and reloading every 30 seconds, but I had to bite the bullet and do that here.
Overall, the random encounter attributes of FO2 can, and often do, create a positive feel to the game. They are also frustrating and annoying (no I do NOT want to encounter a pack of wolves hiding in a field of spore plants). I hope you did not toss your disc, because if you can have the patience to deal with the random battles, FO2 is a fine game. It is not it the same league as FO1, but it is fun it its own regard.
I realize my post comes well over a month after the last reply, but I hope it is still relevant.