Any block cipher in CTR mode can be used to encrypt and decrypt data in arbitrary order.
Basically, to encrypt something in CTR mode, you use the block cipher to encrypt a simple sequence of values, like (1, 2, 3, 4, 5, etc.), and concatenate the results to produce a pseudorandom bitstream, and then XOR this "keystream" with the data you want to encrypt. Since you can produce any block in the keystream at any time just by feeding the appropriate counter value into the block cipher, you can easily decrypt the data in any order.
(Yes, you can even decrypt pieces of data smaller than a single cipher block with CTR mode, even down to a single bit. You do need to compute the keystream block by block, but you don't need an entire block of ciphertext to be able to decrypt it. If reading the ciphertext is much slower than block cipher encryption, this may be a useful optimization, and you can always cache the keystream block in case you need it again.)
The work needed for CTR mode encryption is basically the same as for decryption, and depends on the block cipher you're using. If you can find a usable AES implementation for your MCU, I'd recommend using it; it's a standard, widely used and well analyzed cipher. As they say, nobody ever got fired for using AES.
If AES is too much for your MCU, you may want to look at specialized lightweight block ciphers like PRESENT instead.
Also note that CTR mode does not, by itself, protect message integrity — for that you need authenticated encryption. However, many modern authenticated encryption modes, such as EAX, GCM and SIV, do essentially consist of CTR mode augmented by a message authentication scheme, and thus support all the features of CTR mode (including random-access decryption) once the data has been authenticated. The authentication itself, however, normally requires reading and processing all the data, unless you choose to divide it into smaller segments and authenticate each segment separately.
Addendum: As CodesInChaos notes in the comments above, if the "file" you're encrypting might change, such that an attacker could observe several different ciphertexts corresponding to the same position in the file (encrypted with the same key and counter sequence), then CTR mode becomes quite vulnerable to attacks.
The reason is that, like with any other encryption scheme based on XORing the data with a fixed keystream, an attacker who can observe two distinct values encrypted with the same part of the keystream can recover the XOR of the plaintexts simply by XORing the ciphertexts. If they can guess one of the plaintexts (say, because they know it's all zeros), this immediately reveals the other one. For more information, see e.g. this earlier question.
That said, if the encryption is only done to transfer the file from the device to the host (i.e. the data is only encrypted "on demand" when it's requested by the host), it may be possible to solve this issue by constantly varying the key and/or the initial counter value, e.g. based on a running message counter or a high-resolution timestamp.
For example, assuming that you file is no longer than 64 GB, you could use the lowest 32 bits of the block cipher input for the counter (i.e. the position of the block in the keystream), the next 64 bits for a timestamp or a message counter (make sure it can never decrease, even if an attacker manipulates messages), and still (assuming a 128-bit block size like for AES) have 32 bits left over e.g. for a per-file unique nonce. This would ensure that no part of the file is ever encrypted twice with the same keystream.
Also note that it's perfectly OK to apply this scheme as a second layer of encryption to transfer data that's already stored in encrypted form (possibly also using CTR mode, with a different key and/or initial counter value) on the device. This could afford an extra measure of security against attacks involving physical disassembly of the device and direct reading of the stored data on it.