My answers will be somewhat biased based on my own adventures into rpg development (
http://www.youtube.com/watch?v=olxPQ6zjNEA)...but anyway.
About tile based against free movement: I would say, go for what suits your game best and what you can achieve in the time you have to spare for this project. Tile based movement is easier to implement, 3d collisions are not an issue and you can add puzzles based on the fact that you can only move from tile to tile (like in Legend of Grimrock, which i really love btw). Plus you can edit your levels in an ASCII editor, if you want to.
Free movement on the other hand, is harder to get right and takes more time to implement. If done well, it CAN add to the immersion...but then again, Legend of Grimrock was very immersive, so...
If you watch the video above, you might notice that i'm using a free world but the dungeons are, despite the fact you can move freely in them, based on tiles. That's another option: Use free movement in a tiled world. That way, you'll get the best of both worlds...or the worst. It all depends on your game, i think.
About the terrain, here's what i did (not saying that it's great to do it that way...): I created a terrain in Terragen and reduced the polygon count to make it work well on Android. I then painted a splatting texture which defines grass, rocks, sand and paths. Trees, bushes and flowers are randomly placed but using a defined seed, i.e. each run will create the same random placement. Houses, fences, dungeons, walls, crates...are defined in xml files. At startup, i load these files and create simple beans based on that data. If such a bean gets into view (roughly), i assign a view to it. So my approach isn't tiled, but it's not one (or a few) monolithic mesh(s) either.
Another way of doing it, is what Marlon did with Forgotten Elements (
http://forgottenelements.com /
http://www.facebook.com/forgottenelements)...it's more like the Neverwinter Nights approach that you described.
The best advice that i can give is to go for what you think you can achieve in a reasonable time.