Galaxy Quest
The Usual Suspects
Forrest Gump
Exotica, directed by Atom Egoyan. It was marketed as a soft-core picture about strippers. I was dragged to it by a friend and was very pleasantly surprised. It’s actually a quite moving story about grief and human relations. When you first meet all the characters, you see them as being unconnected from each other, but by the end of the film you learn how inseparably connected they are. (It’s hard to explain without giving too much away.) I now count the movie among my favorites.
Oh yeah, and Lilo & Stitch
Groundhog Day–I expected a typical Bill Murray vehicle when I first saw it (on HBO) but it’s turned into one of my favorite movies.
As a recent example of a film that was OK when I thought it was going to be awful, * Just Married*. Not a great film by any means, but I got dragged to it kicking and screaming thinking it was just going to absolutely suck, and it was actually pretty funny.
A great movie that I only had medium expectations for was * My Big Fat Greek Wedding*. I had no desire at all to see it until all the good reviews came out, and even then I didn’t really expect to like it all that much. It turned out to be one of the funniest movies I’ve seen in years.
Toy Story. I expected to see another Disney animated movie kind of thing. Pixar raised the bar a little bit on what people expect to see nowadays.
Blade Runner. I didn’t expect to get totally immersed in the future world; I expected it to be more of a tv-movieish cops & bad guys kind of movie.
Contact. IMHO the script was subpar, but the acting and direction was so good that the film ended up being decent.
I’ll second Goldmember. It was so stupid, but so funny.
Snatch. Who knew Brad Pitt could be so damn funny?
Bridges of Madison County. God, I did NOT want to see that movie. But I really enjoyed it.
Like Water for Chocolate. Ditto
Also Fight Club- It looked like just another dumb action movie, just another Brad Pitt blockbuster- but actually was thoughtful and is now my favorite movie.
Shrek- I expected animated fare, the standard dull thing, but was pleasantly surprised. Only watched it because my brother had bought it and I happened to be in the room at the time…So I eventually began to like it in spite of myself.
Monsters, Inc- Along the same lines as Shrek…But even better. You’d think I’d be more open to Pixar animation after seeing Shrek, but I wasn’t…again, only started watching because of my brother.
Did you notice the ethnicity of all the actors who played Catholic priests/nuns? 
I’ll add Quick Change, a very funny Bill Murray vehicle that’s nothing like his usual work.
Three Kings. I went to see it because I was working on a project with a girl who was a rabid Marky Mark fan, and nobody would go see it with her. So I took pity. Lucky me!
Recently, Narc. We had planned to see it eventually, sort of, with the guys, but they ended up going without us. So we get this phone call from J almost in tears: “You gotta see this movie. It’s just…” And J dosen’t cry much, but when he does it’s for, well, this sort of thing. So we went to see it mostly as a character study in J, not for the movie, and damn if he wasn’t right. I keep reading awful reviews of it as a genre picture, though. I mean, it is, in the sense that I wouldn’t send anybody to see it who wasn’t familiar with American cop movies, and it’s genre-conscious, using the expected formulae, but I think it knows damn well what it’s doing and makes it effective. YMMV.
Super Troopers. I basically laughed my ass off through the whole movie, and was expecting to MST3K it.
Executive Decision. I gotta admit, I really enjoyed it. And I was expecting it to reeeeeeally suck.
The Ref. If you’ve ever had the slightest problem with the holiday politic bullshit in your family, you must rent this.
Matrix
I thought it would be as bad as every other Keanu Reeves movie.
oh,… and…
Any Given Sunday
I’ll definitely second that. I’d seen the previews and I thought it looked insanely dumb, but my date really wanted to see that specific movie and the only movie I felt strongly about seeing was already started to I gave in. Funniest movie I saw that whole year.
When Mr. Del brought Super Troopers home from the video store, I couldn’t believe it. In a million years, why would he ever think I would want to see something like Super Troopers?
But it was actually pretty funny. Sure, some parts were dumb, but some of the comedy was exceptionally good and downright hilarious.
Meow.
Another vote for Galaxy Quest and Fight Club.
And I just have one more thing to add to the OP…you liked 3000 MIles to Graceland? That’s one of the worst movies I’ve ever seen! Bad writing, bad directing. The pinnacle comes at the end when Kevin Costner’s character, I think, has about 100 police and SWAT team people shooting at him. He STANDS there, firing his one gun at them, meanwhile the laser sights from the police’s guns are ON him, all over his face and chest, yet the bullets seem to go right trough him. Bad, BAD directing. For the love of God, I wouldn’t be so mad if the laser sights weren’t right on him, then it’s as unplausable as any other action movie, but Jesus Christ,
delphica: Eeevil Shenanigans!! 
I’d also like to add Flirting With Disaster. Another sleeper that happens to be gut-wrenchingly hilarious.
Rat Race: The commercials made it seem a lot dumber than it really was. Sure, it’s a take on It’s a Mad, Mad, Mad, Mad World, but I thought it was funny anyway.
The Royal Tenenbaums: I loved Rushmore, but this movie was a lot better than I expected.
The Godfather: My parents have watched it on video for years, but I didn’t catch it until a few years ago. Now it’s one of my favorite movies.
Monty Python and the Holy Grail: A favorite of my dad’s. He tried to get me to watch it for years but I always thought it looked really stupid. I finally watched it and realized my mistake. It’s a hilarious movie!
Tremors with Kevin Bacon and Fred Ward. I went because I love the old horror movies, and was quite impressed with the quality of the piece.