Once you have the headers for the entire chain, you can then ask for the blocks starting with the last block and working back.
How do I keep headers only and discard/reduce the chain itself? Ideally, I'd like to keep by bitcoin folder <100MB.
By "you can", I mean that it is possible to do in principle.
The current client does not do it this way (as you saw).
Bitcoinj only downloads the headers and assumes that it is being used to connect to a trusted node.
You only need your private keys to spend your coins. You only need to make a request to a trusted source of the block chain to learn about payments to you. You only need the full chain if you are solo mining.
But who provides those trusted sources. I wouldn't trust a source that's not e.g. validated by the bitcoin.org website.
If you are connected to 100 nodes and 90 of them are dishonest/corrupted, you can verify that the chain that the 10 honest nodes sent is the correct chain (since it is longer than any of the chains sent by the dishonest ones).
This gets you the main chain, even in the presence of mostly dishonest other nodes.
If a node sends you a block, you can verify that it is part of the main chain by checking the hashes.
This means that if someone sends you the block that contains a payment to you, you can confirm that the block is part of the chain and that it contains a payment to you. After an hour, it will be 6 blocks deep and this is considered confirmed.
If the block hasn't been incorporated into the chain, then you need to make a call on how much you trust the other nodes.
Payments by you can also be verified to have gone through by checking the chain. If the payment is in the chain, then it has been accepted.
The difficulty is combining fast payments with double spending protection. Nodes are supposed to reject transactions which double spend. If this works, once one of the 2 transactions will propagate. If most nodes are dishonest, this could be corrupted and both transactions could be propagated.
However, this will be corrected within the hour as only 1 transactions will become part of the main chain.