I, too, would recommend starting with the Thrawn trilogy. It's not the start of the EU by far, chronologically speaking (set post-Return of the Jedi, that would be The Truce at Bakura, which starts the day after, IIRC), but Zahn's novels started the EU. He did a splendid job, and also introduced a couple of important original characters.
They're releasing a 20th anniversary edition of Heir to the Empire in a few months, btw.
http://www.amazon.com/Star-Wars-Empi...6344888&sr=8-2
If you don't mind reading novels without Luke, Han and Leia (except in a few cameo roles), then the X-wing stories are a must. There are nine novels, and the comics, if you're into that sort of thing.
My personal favorite novels are The New Rebellion (an oldie), Luke Skywalker and the Shadows of Mindor (couple of years old), and I, Jedi. Gotta love Corran Horn.
And I rather like stand-alone novels. After Fate of the Jedi, I really hope they go back to shorter stories, stand-alones or duologies.