I can think of a few good titles...
Ratchet & Clank isn't a sandbox series, though, the maps are pretty wide open. It combines platforming with shooting, and does it pretty dang well.
Jak and Daxter is somewhat similar, but, even heavier on the openness and platforming.
Sly Cooper, I don't know a whole lot about, but, it seems reminiscent of the above two. Though, there's less focus on combat or more on stealth.
inFAMOUS is a series of sandbox games where you've got electric-based super powers, and you get to decide if you're going to be the hero or the villain.
[Prototype] is also a super-powered sandbox game, though, it has more in common with Assassins Creed and Grand Theft Auto, and it's a bit darker.
Crysis is an open-world first-person shooter series, maybe, something like Far Cry. (I haven't played either of these, just yet, ok?)
Batman: Arkham Asylum and it's sequel, Arkham City are all kinds of awesome. The latter is also a sandbox game.
Frogger from 1997 was an awesome throwback to the 1981 classic. It also featured open-world levels.
Red Dead is an interesting series (though, most people only know of the new Redemption installment) of coyboy sandboxness.
Finally, there's Serious Sam. "Why?" Because, of this.
http://www.youtube.com/watch?v=JTbwOukQlDY