The one story I haven't read is getting the most votes. guess I have to read it now. He wrote a great story with Zauriel for JLA called "Paradise Lost" that was great too. Even better if you're a Catholic. Still. I haven't really read a bad thing by the guy.
The Ultimates and Ultimates 2 are 2 of the best stories that I have ever read. I'd rank them up there with Watchmen, Batman: Year One, and The Dark Knight Returns. Mark Millar's written some other very good stories as well, but for me, The Ultimates and Ultimates 2 are his best. I've not yet read Superman Red Son though... I should do that sometime.