Short answer: let Christopher Nolan direct one.
Video game stories mostly suck, and as a general rule they don't really adapt well to a two-hour passive experience. Hollywood invests in video game movies for the same reason they make book and comic adaptations - they have an existing fanbase to work with which can already provide some indication of revenue. The content or quality of the movie itself is pretty irrelevant, even when the movie's downright awful. Exhibit A: The Legend of Chun-Li still made several million dollars in theatres.
I used to think people involved in VG movies don't know jack about the source material, which was true for Street Fighter or Super Mario Bros. Silent Hill and Final Fantasy were made by people who obviously loved the games (FF was written by the same man behind the games). Those are actually decent films, IMO - meaning they have enough dignity to stand on their own without the big-name title. But still, they're far from being good films, and I probably never would've watched them if it weren't for the name. I can't think of a video game movie directed by someone who was considered a "good" director. Maybe that's just what we need, someone who has a clear vision for the project, knows how to run things and most importantly won't want a subpar product attached to his name. Problem is, they never give the director that much power on projects like these. And big name directors would rather not get involved with video game movies seeing their general trend in quality.
Moreover, most videogames are about something called gameplay, and that's completely lost in a movie. So people should forget about making a movie that can recreate the feeling of playing a game. That's just silly. At best, a movie can be a fitting tribute to a game's aesthetics, and provide some amount of fan service. But that's never enough to make a decent flick.
Metroid and Shadow of the Colossus could probably be made into good movies (ANYTHING can be made into a good movie), but if they just focused on just shooting aliens and climbing colossi all the time, they'd be boring as hell. The games can be about that because they have an active component. If you want to make a Metroid or SotC movie, you'd damn better have a clear idea of what story you want to tell and be sure it's a damn good story.
I think we need someone to provide a breakthrough title like what Spiderman and Sin City were for comic book and graphic novel adaptations (or even Tim Burton's Batman). Take a good videogame with a strong aesthetic sense and carry that into the movie, without worrying about staying too faithful to the canon, just take the core values of the games' aesthetics and philosophy and turn them into movie language. Forget about pleasing the fans or recreating the game experience in a 2-hour picture, that cannot be done.
I'm specifically thinking of what they did with the Scott Pilgrim movie, not just transposing the comics into movie scenes but actually making up their own gags and imagery - all of which fit very well with the tone and mythology of the original series. Maybe we just need to wait for someone who actually grew up playing these games to become a successful director.