I didn't want to deal with movement rates and speed. I liked the Microlite movement system where you could move as far as you needed to or as far as I thought would be cool. The bowmen on the stairs are too far away to reach this turn. The Dark Castle is 2 days away, you'll get there around dusk in a couple days (evil laugh).
That's not how the players think however. They want to get up to those bowmen and take them out this turn. They want to get to the dark castle in the afternoon so they can scope it out. They will ask you "how far" and if you show any signs of weakness and mutter some half assed answer like '60', they'll be on you like PCs on a bowman saying "no way! I can run that far in a minute carrying my camping gear to get on a bus!" or "we said we bought the fastest horses in the city! No way it will take 2 days to travel 60 miles!". At least if you have some rules you can point to them and shrug.
I'm not talking power gamers here either. If you are using minis to illustrate positioning this is certainly going to come up. Playing Microlite with my kids and one of the first encounters they had with the battlemap turned into a chase around a couple of trees and they wanted to know exactly how many squares they could move to keep their distance and keep throwing things at the bad guys. I had drawn the trees in just for flavour and they immediately became tactical points in the fight.
I'm not really sure how I want to deal with movement except a vague idea that you can move twice in a combat turn if you want and that it has to be simple. I like the SRD base movement rate of 20 ft. Using minis and a 5 ft. square, that's 4 squares per move or 8 if you just move in that turn. I can even get behind the idea that if you are unencumbered you could move double that, especially if that also covers monsters dropping their weapons and fleeing or fear spells. I would also like to have some differences in speed based on the characters 'quickness' (add 1 square per dex bonus point perhaps?). That means a character with 18 DEX can move 40ft while a character with a DEX of 3 can move 5 ft. (he's real slow to react to stuff, not necessarily physically hobbled). I think I can get away with something like that anyway. I'm not going to get into racial leg lengths or the fleetness of elves or any of that. As for monsters, well you can use their speed out of the SRD* or just make up something. Maybe creatures get to move 20 ft. per pair of legs or something. Flying, swimming - hell I don't want to get into it. Someone has certainly made some charts somewhere.
I also like this idea of move 20 if you extrapolate and say that they can move 20 miles per day on foot (no Dex bonus for non combat movement because you aren't reacting to stuff - you are slogging). That works well for my style and leaves room for the 30 mile per day on horse movement rate that I base my maps on (although I don't know how realistic any of that it is).
As for terrain, well if you are standing on a ledge looking down on the enemy or walking across swampland to get to the castle - this is going to impact combat and movement. How much is the question. And how simple can I make it while still keeping things neato. I think I need to think on it more because I don't just want to be re-writing tables from the Wilderness Survival guide over again.
* I hate leaning on the SRD so much but on the other hand it's a simple web click away and so many of these things have been hashed out for years and are common in a wide range of game supplements - why should I spend a lot of time changing them?