Here's the (quite short) complete list:
Curse of Darkness: this was quite obvious, it doesn't let you see the minimap.
Curse of the Labyrinth: creates a double level, actually merging two layers of the basement. Instead of Basement (or Depths, Caves...) 1 & 2 you get Basement (or Depths, Caves...) XL. If the Basement/Cellar levels are merged this way, both Treasure rooms will be locked. Also you get only one shop and one of each secret room. Some rooms of the level may be connected to the rest through the secret room only, so be careful, since getting trapped with no bombs to get out means that you have to end your run prematurely.
Curse of the Lost: makes the current level bigger by one size category. Basement becomes the size of the Caves, Caves of Depths, and so on. A little example with images:
Tipical Basement layout:

With Curse of the Lost:

Images taken from the wiki.
Also, I managed to play some games pre-"Everything's terrible!" and I didn't get any curse on any level. Even if the sample was small (10-12 games), I can say that the chances are at least slim, if not non-existent, for curses to appear before getting the "Everything's terrible!" achievement.