Well, those first two sound like somewhat contradictory goals.

The programs that give free stays the fastest (such as Choice, Priority Club, and to a very capped degree BW during certain promotions) are in the programs where status doesn't do much for you. And some of those free stays are time-limited, and many of these programs you have to check reviews of the hotel because the quality can vary, so it's a bit trickier to use them as gifts IMHO unless you'll do the research for them or you know that they'll do the research themselves.

Other programs where status does give you a lot (such as Hilton HHonors) don't get you free stays very often. (In Hilton HHonors case, that's partly because your stay earnings are split between Points and Miles.)

Now, let me elaborate more on the capped and time-limited free stays: For example, Best Western currently has a promotion where you get a free night certificate for just 3 stays (which can mean 3 nights if all your stays are 1-night stays). But you can only earn one such certificate, and the certificate is only good for about half a year. (I don't remember whether it's transferable or not.) If you need a free 1-night stay during that time, that can be great. If all the free stays you might need are multi-night stays, it might not help much (if you'd choose a different hotel for all the other nights in the stay, and don't want to switch hotels for one night).

Now, let me elaborate more on Hilton HHonors status: For 16 stays (more nights, so make all your stays 1-night stays to get there faster) you get Gold status, which has basically the same in-hotel perks as the top Diamond status: guaranateed free breakfast, guaranteed free internet, upgrades when available. But how much are these "free" things worth to you if someone else is paying for everything?

Also, that's one thing to keep in mind about status from scratch: You'll have to pay for these things (unless you carefully choose only hotels where they're free anyway, in this HHonors case for exaple Hampton Inns) until you get to your status. That's especially tricky in some programs that don't have a midscale hotel a la Hampton...