But if every client out there deletes the same old transactions wouldn't that be a problem?
It would be a bad thing if an old transaction is totally forgotten, indeed. It's quite unlikely to happen, though. Say the probability for one client to forget a given transaction is p. Then the probability for all clients to forget it, assuming the probabilities are independant, is p^N, where N is the number of clients. So it is quite unlikely.
Does the client not still need to at least initially download and verify every transaction in the chain before it can start pruning?
Normally, yes. But I'm not sure it's absolutely necessary. If a spent transaction has been forgotten by all the network it means all clients have agreed to acknowledge this transaction to be valid and the bitcoins spent. So you have to trust the network as a whole, as you do when you suppose that a majority of the computing power is honest.
Would that introduce reliance on central servers who store the data everyone else is deleting?
Such servers would not be "central" since anyone could make one at any time.