Without a doubt the best voice acting I've ever heard in a game for every character no matter how small or large was Grim Fandango. You can't meet a character without a unique accent or personality, and every word is acted as if it's being performed in a film. Of course the great thing about those kind of adventure games is once you've got the actual interface done you can focus a lot on the rest, and the interface tends to be simple and based on the previous ones so they can put a lot of effort into things like style, graphics and voice acting. And when you pick up something that you decide you don't need and your first thought is "No use for it" in a spanish accent, you know it's made an impression on you.
My next would have to be Beyond good and Evil. I remember the little satchel guy and Pey'j and Jade all being very distinctive and well done, especially for the time, but I think it still stands up to the times, if not even better than many still. Though I think in general the voice acting is progressing at a very slow rate. Even the biggest name games these days don't, to me, stand up to these two, and one of the reasons I'm willing to play them repeatedly, no matter how much I've memorized the content and answers to all the puzzles and secret locations, is that the voice acting is just that good and I'd love to hear just one more time "Run you pigeons, it's Robert Frost!"
By the way, since many people have mentioned MGS, did you know David Hayter co-wrote the script to Watchmen? Though really editing is mostly what he did since a lot of the dialogue is word for word, but I just thought that was neat when I found that out.