A game from the Castlevania series immediately springs to mind; there's a reason they call them "Metroidvania" titles - they have that open world platforming aspect you're looking for. On the DS, you can pick up Dawn of Sorrow, Portrait of Ruin, and Order of Ecclesia. Of the three, I'd recommend starting with Portrait of Ruin - DoS has aggravating touch screen mechanics for boss battles, and OoE is absolutely brutal at times, so it's not the best to start with it. PoR is the comfortable middle ground - challenging but not unfairly so, no annoying gimmicky controls, and a passably good plot which crops up from time to time, and a relative degree of freedom to challenge the areas in whatever order.
If you've got a DS and not a 3DS, you could try the GBA titles as well. Aria of Sorrow is easily one of the best instalments in the franchise, and Harmony of Dissonance has an absolutely massive map. Circle of the Moon is just cruel, though; I wouldn't recommend starting with that one either.
You can pick up Symphony of the Night off the PSN for the PSP too, although whilst a lot of people claim it's the best one, I think the controls feel a bit dated; go with one of the DS versions and see what you make of it before going for this one~