How do APIs like Blockchain.info and BlockExplorer work? When I query an address using either service, are they simply querying the latest block that has been mined?

Or do those services have nodes in the network that collect data that has not yet been codified in a block?

Sometimes, my queries return the "correct" information nearly instantly, but sometimes it takes a long time for the most recent transactions to be reflected- wondering why that's the case. Seems strange that I could send btc, have a query on the receive address return the up-to-date balance within 3 seconds, and then immediately make another transaction and make a successful query, whereas at other times the API query won't reflect the latest transaction for a long time. Insights appreciated.
Public Bitcoin inspection services like BlockExplorer and BlockChain.info work almost exactly like the regular Bitcoin client.

They operate as a node in the Bitcoin network and so, like all other nodes, store the complete block chain. This block chain consists of all transactions ever made and are used to calculate the balance of an address.

Just like other nodes, they as well receive transactions from other nodes and will likely also show them before they are confirmed (of course explicitly indicating they aren't). The time it takes for a transaction to reach all nodes varies. Not all nodes know about all other nodes so it can take a few seconds for a transaction to get noticed by all nodes.

Depending on whether or not the service caches information, some time can be between the arrival of the transaction of the node and the time it shows up on the website. You will probably understand that when you query 10 times shortly after each other for the same data, it is very costly to do the same lookup in the block chain index multiple times. Because of this, I think it's likely that most of these clients do some sort of caching, but not too extensive. Probably a minute maximum, because they know that in Bitcoin transaction processing, much can happen in that time.

Besides that, the loading time can also depend on the load of the server. When multiple users try to access the balance for their address at the same time, some of them will likely have to wait.