Best stories and characters, huh?
One of my favorites will always be Dark Cloud/Chronicle. The stories and characters in the series are done quite well, it realy does disappoint me that the actual gameplay can be hit or miss for some people. Really, the only issue I take with the story is the whole, "hijacked by gannon," bit that happens at the end with no real build-up. Sure, the first one kind of had that, but it was hinted at enough.
I also love the story of Kingdom Hearts. Sure, it can be very kiddy at times with the Disney and FF characters, but the original characters they made have such fantastic moments. Their stories can be really touching at times and the plot that revolves around them can be quite good.
And say what you will about the change in gameplay, but I think Super Paper Mario needs a mention. The individual worlds can be rather forgettable at times, but I'll always remember the main plot of the story with Black and Tippi. It was sappy at times sure, but it really did top the plots to the previous games so easily.
There are others, but I'd rather not repeat what will already be said.