What is the best way to download a "recent" UTXO set snapshot? I am using bitcoinj to listen for payments. I need a way to maintain the entire UTXO set in a local database. 


Can bitcoinj be used to download every block (I think it downloads only recent blocks and headers for older blocks)?
I don't need to use bitcoinj or even Java for creating or maintaining this database if a better solution exists. Is there anything like this? 


Ideally what I want is a wallet that downloads only the UTXO set without downloading the entire blockchain (due to bandwidth limitations) and maintains it from then onward. This needs to be the entire set, not just for the addresses I own. 
Additionally I need an API that allows for following queries:


Given a UTXO, check if it is present in the set.
Given an address, get me all the UTXOs for it.


I think that it is currently not possible to validate a given UTXO set without downloading the entire blockchain, so some solution in this regard would also be appreciated.
Yes, by default bitcoinj downloads full blocks, from the Genesis. Only if you connect a wallet it uses optimizations like checkpoints and filters.

Just downloading the UTXO set (in a trust free way) isn't possible, because the Bitcoin protocol isn't designed for that. You can get UTXOs from block explorers and Electrum servers, but it will be without crypto proof.