Well, there's room for refinement, but I did a quick-and-dirty map generator that creates a ragged coastline around the overworld and then seeds it with a mix of mountains, forests, and lakes, then crosses it with rivers, passes through the mountains, and roads. Each land form has a slightly different process for generation, in order to give better results.

There's room for some refinement, but it hits the high points:

1. You can find the basic four landscapes (water, plains, forest, mountains) anywhere you go, in slightly different proportions.

2. It's navigable. The frequency of obstacles means you have to explore... you can't just hold down a key and make it from sea to shining sea. But it gives you a world that you can find your way around.

The results aren't exactly the most beautiful examples of video game cartography, but they never were going to be. They are in the neighborhood of "good enough by Ultima Trilogy standards", which is really more what I'm going for.

Now, my current model for the world has it that you go up in difficulty level of encounters by going away from the center of the map. If I used the whole of a 1,000 square landmass, this would mean that if I fit 10 levels of content into it you'd be switching levels by going about three screens in any direction. That seems a little abrupt, and it would only get worse if I added more content.

So I'm going to start with five levels of content in the first landmass. After that? New landmasses, either using a "sail off the edge of the map" mechanic or some way of accessing them via portal or tunnel or something. Actually, I'm kind of partial to the idea of borrowing the tower of worlds from the Final Fantasy Legend/SaGa games... put the tower somewhere on the coast of the first world, and then in the center of each subsequent one. Your character could only ascend to the floor equal to your level, and there would be an out door to a new world every 5th floor, starting on 1. (1, 6, 11, etc.)

Or alternately the tower would be the mechanism for getting from world 1 to world 2, and subsequent worlds would have their own schemes.

Because leveling up is item based (collecting Phosphor Essence), I could still keep my plans to release content incrementally... put the tower in at launch even if there are only five levels of content.
I'm sure this isn't the type of feedback you're looking for, but those graphics are bugging me. I get that it's a particular style but the turfs look too simple and tile-based compared to the mob, who is holding a sword that extends outside of its tile (and, in theory, is an overlay that'll change depending on what weapon the player has equipped).

I'd make the water tiles autojoin so the coastline and rivers have rounded bends instead of sharp corners.

I'd also use varied icons around the edges of things. For example, have a set of mountain icons that only contains three mountains (instead of 4) and use this icon for mountain turfs that aren't completely surrounded by other mountain turfs. This way it'd look like mountain ranges thin out around the edges and aren't so tiled. The same could be done for forests too.

Other than that, the environments do look nice =)
I actually changed the landscape icons a bit after I posted that... I decided to go away from the representation of mountain peaks and instead make them into a "rock" terrain that is blocky and impassable.

The big rocky outcroppings can be read as a mountain by the player, but this makes the fact that you can break them down and harvest them a little more plausible, and opens up possibilities of getting up on top of it and moving around. I've also added a very simple border around the rock tiles to help make it stand out more from the trees, and I'm going to do the same thing with the water. Not a traditional rounded autojoin, but a clearer boundary. "Round" corners aren't in the cards... I've been looking at taking a square sized chunk out of the elbow of the bends, but I'm not sold on it.

It's my intention that the landscape looks flat and primitive in comparison to the (not exactly modern and flashy) PCs. Since everything's one color, making characters pop out of the landscape isn't a bad thing, to my mind... the effect is actually muted in these pictures because I didn't bother to customize my icon or gear up.
I'm not sure if taking square chunks out of the corner of water tiles is consistent with the rest, but as long as you're still open to changing the graphics I'm sure it'll turn out ok.

It's my intention that the landscape looks flat and primitive in comparison to the (not exactly modern and flashy) PCs.

I don't see that here. I could understand that concept if it look like a board game where the turfs would look like painted images on paper and the player's icon would look like a game piece standing on it - the turfs could use very muted colors and the player's icon would be bold with a thick outline. Everything here looks flat and primitive =)

Are you considering adding more terrain types? Just having some additional types of tiles could help a bit.
I'm not going for a board game effect. I just want the player to stand out slightly while not being wholly inconsistent with the graphical milieu. It works better when the icon is customized... just the addition of a hat works wonders.

The basic landscape is not going to be much more diverse, but there are going to be more details scattered throughout it... bridges, paths, odd rocks and growing things. The forests in particular will look more organic when you actually play the game because they can actually grow outward by individual trees.

My graphics have gone through a lot of evolution. My first attempt at the trees and mountains were actually a lot rounder, which gave me the impression of someone using an old green monochrome monitor to try to emulate a more modern game... the exact opposite of what I'm going for.

The bottom line is that I'm not making this game to impress people graphically. My target audience is people who feel a booster shot of nostalgia when they see green tile graphics.