yeah, the 'tower stepping' tactic could be an issue. I wouldn't really want to see all important field battles become tower sieges.
Having a tower be 'under construction' until your next turn isn't that far out. Like you said, unit production works in a vaguely similar fashion. Still, I agree that it does seem slightly less intuitive than the 'instatower'.
The 4 movement thing might get confusing, and has some exploitable loopholes..plus it makes fast units even better (which doesn't need to happen).
Maxing the number of towers a player could build to five could work. It does seem very rigid though..a bit of a brutal solution.
Maybe each tower you build costs an extra 100 gold. First tower costs 100, second 200, and so on. That would allow a player to go crazy and build tons of towers, but it would get very expensive.
Another way to work it would be to have a special unit tied to tower construction. An engineer, or builder or something along those lines. You would purchase the builder in the same way you purchase other unit production. A builder would move to the location you wanted to put your tower, and would then be consumed and replaced by the new tower. Perhaps, only one builder could be produced. You would have to buy the production again in order to build another.