When should I use a workshop instead of a cottage?
Workshops make a good improvement when you need the city to be production rich. They are especially good for non-river, flat tiles when you're running state property, which itself is good for a large or spread out empire, i.e. when you're going for domination. Due to caste system, more workships will also be built on a cultural victory game. Caste system is useful for cultural vicotry due to unlimited artists in your gp farm city when you would otherwise be limited to two.
Cottages are an investment and, given time, will turn into awesome commerce tiles. In at least a few of your cities, half the tiles should be towns. The towns will later net yields comparable to a gold resource. But sometimes even cottage cities need to build something like libraries and universities, so the other half of the tiles will be production tiles supported by food resources. In absence of hills, a workshop may be your best option.
When should a windmill go up instead of a new mine? Are there instances where I should replace one with the other?
Several factors:
Replace growth-limiting mines: When you look at a city, you need to determine if it has a food surplus. Can this city grow to 20+ population eventually? If building mines would limit the potential growth of the city, build windmills.
Is my leader financial?: With electricity, financial leaders will get better yields from windmills than other leaders. A grassland hill next to a river makes a good place for high-yield windmills if your leader is financial even with machinery alone.
The resource factor: The long-term advantage of using a lot of mines is that they may randomly acquire a random mine-based resource you have the technology to see. I have been told that the odds increase as you learn of more resources that can be mined. So if you don't have gems, silver, or gold, one of your many mines may randomly find one of these resources eventually. It's not something to count on, but it's a consideration. It happens at least once, but more often 3 or 4 times in most of my games, but it's not necessarily a resource I didn't have. Also if you discover a resource via new technology and a windmill is already on it, you'll usually want to replace the windmill with a mine.
Technology factor: I alluded to this a bit before but windmills are enhanced further by electricity with extra commerce, and replaceable parts with an extra hammer. Also, windmills get a further commerce boost with environmentalism, enabled by medicine. Mines become more likely to pop resources as you discover technologies that reveal mine-based resources (bronze working adds copper to possibilities, physics adds uranium, industrialism adds aluminum). Mines get an extra production with railroads.
It all depends on if the city needs food, commerce, or production.
And what the heck do Waterwheels even DO?
They add only 1 extra production to the tile at first, with the idea that production is being supplemented by a wheel turned by the river. You can only build one per tile-length stretch of river, i.e. you can't build them on river bends or across from another watermill.
Watermills become more worthwhile with replaceable parts and electricity. They're usually the best thing to build where you can when you're running state property due to the food bonus.
If I have a plains/forest/hill/rive tile in one of my early cities, I try not to chop it because I know that, optimally, it will produce the most hammers with a lumber mill. But I also know that, until I get to those techs, it's producing far fewer hammers. To chop, or not to chop...
Keep in mind that each forest gives you a half a healthy point, rounded down. But lumbermills do not yield more hammers than mines, they simply allow you to keep the healthy bonus with equal production yields.
I try to chop forests in a checkerboard pattern to maximize regrowth rate in unused tiles, but don't sacrifice short term growth for long-term growth or hammers. I often leave exactly 2 forests in most cities for the endgame, but far more wherever I want to put the national parks wonder.
Also note that when timing chopping look for bonuses: imperialistic leaders will get more out of it when producing a settler, industrious to building a wonder... the base rate for chopping will go up with mathematics, but you may need/want to chop earlier, for example when you really, really need a wonder like great lighthouse on archipelago or great wall on pangea.
for workshops):
5
counts separate from each other. When it comes to hills, IMO 
