Shadow of the Colossus is free-roam, lots of exploration, and "real time." It's a beautiful, haunting game. Vagrant Story is similar and has a very intriguing story.
Parasite Eve is a sci-fi horror RPG series you might like as well. Not terribly roamy, but the story's good and I enjoyed the combat. It's for the PS1, and has a sequel also for PS1.
The Mass Effect series and Dragon Age are also pretty gripping and are real time. Dragon Age is obviously the more traditional sort of RPG and has SCADS of side-quests, so it'll last you a good long time. It has a good story, too, and an expansion is coming out in March.
Despite your "not an FF kinda guy" thing, if you haven't checked these out, you might--they're pretty unique. Final Fantasy Tactics (the original one, and still the standout) is great for tactical (durrr) battles, has a tight story, has lots to do, but isn't "roamy" in the traditional sense. Final Fantasy 12 is a good "roamy" game and plays similarly to Dragon Age, with programmable allied AI, shit tons of sidequests, and beautiful environments. Loooots of roaming. And sky ships. Both games should give you some challenge.
Sadly, you nixed cel-shading and anime style graphics, so the Persona series won't be for you. The games have great stories, slick art, side quests, wonderful character development, and a pretty unique style of play. Plus grinding, which I'm given to understand that some folks really enjoy.