Sure, search for Isometric tutorials, top down tutorials, sprite based tutorials, grid based tutorials, tile based game programing tutorials, jrpg tutorials, etc.
If you've done all those things a 2d sprite game is not that different from your sonic game. Take away the gravity and optionally "lock" the user to a grid for the first Zelda and you're most of the way there. :)
You might take a look at some 2d XNA tutorials. I find working with their SpriteBatch pretty easy. The tile engine tutorial series is pretty good.
http://www.xnaresources.com/default.asp?page=TUTORIALS
I'm not sure how easy it will be to translate over to Allegro, but it would be a good learning experience to see how it works in one library and think about how to make that work in another.
- Eck