Instead of checkpoints, client could hard-code a MAIN_CHAIN_MIN_POW variable.  This would be the PoW of the main chain when that version of the client was released.  All clients wouldn't need to agree on a value.  It is just a spam protection value.

Clients should download headers first and only commit blocks to disk that are on a chain that has PoW higher than the hard coded minimum.

Clients should respond to "inv" messages containing unknown block hashes by sending a "getheaders" message rather than asking for the block.

If the block extends your main chain, you will be sent it.

Peer sends: "inv" containing unknown block
Send to peer: "getheaders" with standard block locator (send at most once per inv message received)
Peer sends: "headers" with new blocks on it's main chain
Add these headers to header tree
If the main chain is extended and the main chain has PoW greater than MAIN_CHAIN_MIN_POW, request those full-blocks
...
No matter what happens, the longest chain will always have more PoW than the longest one when the client was writen, so the best chain is guaranteed to have more PoW than MAIN_CHAIN_MIN_POW.

The client won't consider itself synced unless it is on a main chain with PoW that exceeds that value.