Sounds like a fun idea.
Instead of making a large storyline for the whole game, focus instead on a suitable story for a demo. Create a simple but memorable character, a small scale event to drag him/her into, and a quick resolution. Later, in the full game, this character could make a small cameo or something.
Here is something off the top of my head.
A wizened old drifter scrapes his way into a dusty, barren town on a cold night, and spends his last few coins on a late dinner and a dingy room.
As the day dawns he wanders out into the scrub in search of water, only to discover the riverbed has completely dried up long ago.
Asking around the town, he learns that the spring in the nearby hills was buried by a band of trolls.
Hm, getting off track here, but something simple like this will serve fine.
Couple of guidelines -
stick to creatures and people included in the RPGMaker RTP sets, or something similar. The animation is set up a certain way, and it'd be lame to have some units be totally different graphically.
Similarly, the setting must be in a geographical location included in RPGMaker. The desert town set is not well fleshed out, etc.
A cave would be cool. And easy.
About the pacing and difficulty of battle -
I envision battles involving up to 18 units, a limit which I intend to reach fairly quickly. I like the concept of a small scale skirmish.
If I do a tile approach, I'd like between unit scuffles to last several turns at least, with time for planning the opening tactic, time to try alternate tactics, and time to move another unit into the action.
However, if the pixel based thing works out, I would prefer to create a single main character. The AI for multiple pixel based combat units would be pretty complex, imo. With a single character you could do some cool lone wolf thing. You could always allow the character to summon other creatures, who would have limited capabilities (thus simplifying the AI). Also, manipulating the enemies would be central. Traps, slowing effects, artificial summoned barriers, illusion magic, all of these would fit well with a single unit running around the screen.