I could be wrong, but I don't believe you were able to buy unlocked phones with no crapware, as part of the normal subsidized phone regime most carriers have. Yes, you could always pay full retail for virgin phones, but most phone sales occur through channels that are structured around seriously reducing the cost of the phone in exchange for signing a contract. Apple was, IIRC, the first phone vendor to participate in those high-volume channels without locking or crapware.
iPhones have had locking from the start. You are correct about crapware however.
That said this conversation is about unsubsidised, unlocked phones. Not phones bought through carrier channels. Apple are breaking new ground by selling an "unlocked" phone, for an unsubsidized price, but still pushing carrier restrictions on it.