Okay, I’m about to flood you with links and rabbit holes. 
First off, I would be remiss in not pointing out Alex’s own Segreta, which must have some interesting dungeon generation war stories. 
Unfortunately, Dyson isn’t active around here any more, but he used Perlin noise to generate some stuff in his MTE, e.g. here was one of his responses to a question of mine. I see some other info elsewhere in that sub-forum, but some of those topics are huge and the posts themselves are walls-of-words, so not a quick and easy search. 
I am definitely familiar with simplex noise! I have a Corona-compatible version in Lua here, an earlier version of which appeared on the old Code Exchange. The module dependency can be replaced with the Bit module; it’s general-purpose enough that I don’t want to introduce a hard Corona dependency, is all. I have also been adapting some noise code for use in shaders as well (very little of this is my own code, so see the attributions inside).
If you go the LuaJIT route, the Lua module actually began life there. Unfortunately, I haven’t had much excuse to play with it recently (ditto LuaJIT more generally), so my most up-to-date code (plus commentary) is actually found here; I should probably report some of that back to Dr. Gustavson, one of these days! (I also have C# code, but never got it production-ready, really.) Also, if I remember correctly, Dr. Gustavson did like to hear about simplex noise “in the field”.
I forget what got me looking into simplex noise in the first place. Near as I can tell I must have done further research after reading posts like this and this. (Excellent, excellent dev blog. It’s too bad he’s been quiet, lately.) Sooner or later I mean to pick up this book as well, which may also have mentioned it.
I do know, however, that he tipped me off to easily seedable (but still high-quality) random number generators like those of Marsaglia (current code here), which I imagine you could also incorporate into your toolkit. I believe roaminggamer uses another technique as well, based on one of the hashes in the crypto library. (Also, if you’re willing to backport it to Corona’s Lua 5.1, Dirk Laurie posted an implementation of ISAAC on the Lua mailing list, a while ago: ISAAC in Lua)
Food for thought: Generating Complex Procedural Terrains Using The GPU (Some of the required features might be available on more recent devices via GLES extensions. Unfortunately those tend to require a little native-side assist.)
There were some interesting ideas here: Herringbone Wang Tiles (I am almost certain this is what led me to my own current expensive problem, with the Fast Fourier Transforms. In at least one of those articles, Sean mentions colored corners, which I have partially implemented. I was doing the texture synthesis, but the authors describe Poisson disk applications as well. I need to do some restructuring for the texture refinement passes, but have a functional first pass. Unfortunately I got totally railroaded looking into some of the computation-heavy stuff for non-random texture synthesis. )
Err, and I never did give a “how to make a city” link. Alas, I do not know one!
Anyhow, I hope something in that was useful.
EDITS : Cleared a couple things up, fixed links
