Compared to Windows SIDs, Linux's 32-bit uid is a "smallish integer"

Yes and no. Bear in mind, a large part of a Windows SID is a namespace - the actual id within that namespace is so far without exception under 32-bits. An entire Active Directory domain (read: single domain, not forest) is actually limited to 2^30 RID's being issued - after which no new accounts (including computer accounts) can be created, period. You can technically unlock an extra bit and issue 2^31 RID's starting with WS2012, but compatibility is a potential issue and MS's documentation says you should only use it while planning a migration to a new domain (and for good reason).

This does technically give Windows some advantage here as SID's are namespaced - you can have multiple domains in a forest, domain trusts, etc - but I don't think as far as realistic number of users accessing a network it makes much of a difference.

Where it does suck on Linux, however, is user namespaces. 32-bits is a lot when it comes to just giving out accounts, but it's nowhere near enough to give every user a 16-bit chunk of accounts for mapping the traditional 0-65535 (because nobody) ranges for use with unprivileged user namespaces. I'd really like to see a push for 64-bit uid/gid's for this reason.

And yet in practice the only problem with them is when mapping Windows SID is needed. Otherwise, they are fine.

Also, Windows SIDs are fixed-size 128 bit. They were supposed to be GUIDs, but they are not that random; user SIDs contain common prefix from the domain SID.