Ultimate History of Video Games is pretty good...it's what I'm reading right now. I think that one is held in high regard. It starts off wayyy back, like in the days of pinball, the creation of Spacewar, etc., but it's all fairly interesting.
All Your Base Are Belong to Us, despite the shitty name, wasn't too bad. Some reviews say the author pulled some details out of his ass (as far as conversations, etc.), but I have no idea how accurate that is. Still fun to read. Starts really early in the history of gaming, just like the other book...starts out talking about Ralph Baer, I think.
Also bought ZAP - The Rise and Fall of Atari, but haven't had the chance to read it yet.
One of these days I want to get that Game Over book...sucks that it's out of print.