With Starwood, the upgrades flow to the Platinums and above, so you'd need to commit 50+ of those nights to SPG. (You could reach Platinum in 25 stays, but I assume a mostly-leisure traveler would tend to average 2 or more nights per hotel.) I don't know how many true 4-stars exist in the SPG system, but I know there are some.

Starwood is a very rewarding program, but you do need to get to at least the base Platinum level to start getting good upgrades.

If your travels take you to too many places that don't have a Starwood, you might instead consider HHonors. They have a variety of fast-track type options to Gold, which gets you *some* benefits. Gold tends to be treated fairly well outside the U.S.

Having a backup with a huge volume of lower-end hotels can be helpful. I've used Priority Club points at a value of a little under a penny apiece in rural areas where no other brand had properties. Carlson seems to have good utility in Europe. Don't know much about Choice...