I've seen a handful of game request being rejected due to server protection. What exactly does it mean? Do they require connecting to the game's specific servers a la Ubisoft or something like that and don't function offline otherwise?

This is achieved by the game developers using their own servers and verification systems. Since they have their own security measures in place they do not use Steam servers and this allows them to verify license ownership online. For some games single-player mode works, while for others server verification is required for both modes.