Other than a few things from Shadow Kami, nobody's done any of the tiles yet. Some elements likely to appear in the game: Deciduous trees, palm trees, bushes, rocks, beach sand, waves, a lighthouse, a sunken ship, a non-sunken ship, lava, giant light bulbs, haunted house stuff, falling chandeliers, broken bridges, cacti, and quicksand. Feel free to experiment with different styles, although I'd like it if they'd look natural in a game window of at least 480x360.

Sounds good! I could start on the character and some tiles for the grass world. So, 32x32?
Also, how much realism should there be? Are you wanting to make something serious or goofy?

Finally, do you have any designs for the character yet? Are you thinking an average guy, a buff guy, a guy with crazy hair, etc.?