I find stories to be strong if they're character based (and I think it's probably easier to do). If you can come up with some interesting motives (motives shouldn't be all of your character development or near it but it can be an easy way of making very interesting ones) for a set of important people and find a way to toss in a main character then the story shouldn't be too hard. This gives a nice feel of the story being intertwined with characters that works really well. I'd also try to design a world that has some very contrasting parts that can develop feel for the game. A place like Midgar (FFVII) with it's social structure (the plate and the slums contrast nicely) or the difference between Garden (FFVIII) and FH really add something to a game. Gameplay is also very important but I'm guessing you'll be doing a standard rpg system, which I can't help with.

Another suggestion would be starting an RP here to try to create a world. This doesn't follow my idea for motive based characters but people make distinct characters generally following what they think is cool. This could spark ideas and controlling NPC's to to get better at making allies, enemies or people just in the city will probably help your rpg.

Creating a feel for the game with motive based characters in a thought out world if done okay would probably be the easiest way to get me to like a game. Other important things would include: gameplay, graphics, ending, opening section (getting them caught into the game and storyline), spread out character development (making it not all at once and so the spotlight won't be on a single character at a time).

I think some games that show examples of certain things well done are:
Final Fantasy Tactics- Story based around the motivations of the individual characters.
Vandal Hearts- Motives are done reasonably, but there was one part of the story that struck me above others (and I wish it had been expanded on) that there had been a revolution that the people believed couldn't be wrong as it had disposed something terrible. Nothing to do with it could be faulty (this stopped pretty quickly so I wish it had been better done) and people were quite naive when it came to it. But this wasn't made the point of the game (and it shouldn't have been) it was an excellent side touch that changed everyone's portrayal of events. My idea with this is to have some large event that people are naive about, and to use it as a tool to slightly change how the main character learns about events. This doesn't need to be important in itself but having it effect other stories would be very interesting to see done well in a game (this makes me want to start another RP).
FFVII- The idea for Cloud's history is a very interesting one. The idea of forcing yourself to believe a lie until you've lost what really happened or your perception of such is a realistic concept that can be used in a lot of ways.
FFVIII- The way Squall thinks about a world so different from what I'm used to made this game my favorite game of all time. This is also had an ending wonderful to watch.
Other FFs exemplify important qualities as to other non-ffs but there's one game I want to mention that I will not stop promoting:
Shadow Hearts: Covenant- This shows so much, from that amazing ending to the humorous touches, the character development and the different feels of the game, the connections with history but following it's own path. If I ever made a game this is the kind of game I'd love to be part of.