In your Steam library, you can right-click a title and select Properties. From here, select the Updates tab.

In the bottom part of the window, you can see exactly how much space is used for that game, and how much storage that game has left. Here's what it says on my computer for [SpaceChem](http://store.steampowered.com/app/92800/):

![Properties dialog for SpaceChem: Steam Cloud: 1.27 MB stored / 94.10 MB available][1]

As you mentioned yourself, the permitted size does indeed vary per game; e.g. [Portal 2](http://store.steampowered.com/app/620/) has 1 GB available.

I assume this information is also available even if the title isn't currently installed, but I have not tested this.

  [1]: https://i.sstatic.net/3UKpv.png