I find myself clicking Large then Small to rebuild a Small city since Rebuild doesn't seem to do anything.
"Rebuild" uses the seed of the current map, so it produces roughly the same city. In a way if it does anything, it's a bug. This button may be useful when you want to adjust the current city: change the number of roads, toggle city walls etc.
If all you need is a new city, use size buttons (Small, Medium, Large), click "New city" in the context menu or just press Enter.