I think I have similar aims to yours, so I have a few thoughts which may be useful.
To my mind, what gives the sense of adventure in Overgrowth is a combination of dynamics (both physical and conceptual - freedom of movement and travel, as well as every object being a potential threat or opportunity) and immersion (view distance and naturalistic artwork).
Otherwise it combines familiar themes from 2D games (button combos from fighting games, and use of vertical space from platformers), which are easy to replicate. This may be an important part of what gives it a sense of adventure - using familiar techniques in a new kind of setting. I think it is essential (it is clearly an important aim in developing Overgrowth too) that it puts you in the boots of an explorer, who may be defined as an individual with knowledge of a range of relevant subjects and experience in survival and problem-solving, who seeks unknown environments and experiences.
Given this, it seems that the thing to do is to give the player a familiar toolset (running, jumping, fighting, hiding, crafting, etc.), and put him in a new environment.
Here are my ideas :
- Ditch the platform. Use more organic polygonal shapes for your levels, to create a more varied, lifelike, and engaging environment. Ditch the moving platform too - an explorer does not wait for a platform to descend and take him to the top of the mountain - he devises his own means. Note that if the player has tools which allow him to deal with any situation (when used intelligently), we have much less to fear from procedurally generated terrain, which can offer some useful surprises.
While we're here, ditch the map. It tends to detract from immersion. A very wide level gives a much more seamless experience, with portals allowing access to other levels if necessary. Assuming we want crafting, vehicles make an interesting mid-game goal, although they should be treated cautiously.
- Peek ahead. As alluded to above, give the player the ability to see into the distance, but not in detail. Perhaps even force this by having the camera zoom out if the player stands still (or some similar cinematic mechanism), but limit this ability, so that, for instance, you can see far-off terrain, but not objects. Assuming that exploration is in itself the goal, the player must be enticed with the promise of revelation, which boils down, in mechanical terms, to seeing distant terrain, buildings, caves, etc, but not their inhabitants or contents. Consider rendering only visible or discovered objects, as in a stealth or fog-of-war scenario, or in some other way concealing enough to leave a few surprises.
Another way to do this might be to use carefully planned backdrops which depict the area ahead in the distance.
- Grow and change the world without necessarily waiting for the player's direct involvement, to provide a continuing challenge, and prevent boredom. Cycles of day and night, seasons, population growth, etc. can be easy to implement, and may be particularly important in a 2D environment, which naturally feels less life-like than in 3D. On that note, don't skimp on organic elements - consider how many people talk to plants, compared to how many talk to crates.
- Think carefully about rhythm, and allow the player time to take stock and make plans - the balance between fighting monsters and smelling flowers should provide something for everyone, or narrow down the target audience.
- Reward exploration with new and varied encounters. Give the player genuine discoveries. If all I discover is that wherever I go I get attacked every 15 seconds, I can assume that that's what will happen to me over the horizon, and have no need to explore, because I already know what lies ahead. Similarly, allow the player options for interaction (chop down the door, pick the lock, find the key, get the guard drunk, etc.).
Visuals are also very important, of course. Put plenty of effort into blending artwork and ensuring a sense of depth. Awe-inspiring vistas are great too, but stay away from photo-real graphics, which always look surreal and awkward. Even fairly simple stylized graphics tend to work better if they are unified.
I hope that some of this is useful (I'm sure it has been for me), and look forward to hearing what you have.