Good topic. Of the ones already mentioned, I'm a fan of Bean, Cox, Skaarsgard, although I think they are pretty well known. Also like Stormare and McGill.
Some of my favorites (not all of them are in a ton of movies, but generally lesser known actors):
Zeljko Ivanek. Most well-known from Homicide: Life on the Street, although I haven't seen it. I enjoyed his work in A Civil Action, 24 Day 1, Dogville, The Manchurian Candidate.
Chiwetel Ejiofor . I've only seen him in Melinda and Melinda but was impressed, I need to see Serenity and Inside Man.
Djimon Hounsou. Liked him in Gladiator and The Island. Needs more big roles, even if typecast, makes a badass assassin/mercenary type.
Ciaran Hinds. Munich and The Sum of All Fears.
Michael Cudlitz. Most known from Band of Brothers. Also in The Negotiator and has had small parts in a lot of TV shows, ie 24 and Prison Break.
Jason Isaacs. Probably better known than the above actors. Blackhawk Down, The Patriot, Harry Potter.
Gong Li. One of the most famous Chinese actresses and is in many of Zhang Yimou's films, not as well known in the states. Probably too famous for this thread but worth a mention. I think Memoirs of a Geisha was her first major Hollywood role, and she'll also be in Miami Vice.
some others: Xander Berkeley (24's George Mason), Robert Patrick (T2's T1000), Jürgen Prochnow (Das Boot)