I usually only build them after Rep Parts. However, often what I do is pre-build them on appropriate hills and then complete them later when RP arrives.
When building windmills, you have to take a good look at the city specialization. Also, what victory are you going for. They are great for late space game to grow your cities onto even more production and specialists. Also good for late game Domination milking to just grow cities as large as possible for score. If going for fast military victory, windmills often just don't come into play and the extra production from mines is more valuable, especially in an HE city. Likewise, with Culture games, windmills are usually don't factor in much either.
I generally only place windmills on riverside hills, especially river grass hills, as they rock with windmills after Rep. Non-riverside hills are served best by mines, especially plains hills, and the boost they get from railroads. However, it depends on the growth needs of that city. If a windmill allows a production city to grow onto another mine, then the net affect on production is higher.
Pre-Rep windmills would be rare for me. Only in the case of a city sorely lacking in food.