Proper encryption algorithm to use when encrypting data before backing it up to untrusted hosts? I'm writing a (non production/proof of concept) backup program that takes files from your computer, splits them into blocks, and then has other peers store those blocks to create an offsite backup.

Those peers could be other parties that you would not want to disclose the contents of your backup to.

These peers work in a peer to peer fashion, allowing them to get a copy of a block from anyone who has a copy. This means that a peer that is replicating a backup could connect to the machine that is being backed up and request a block from the middle of the file.

So, it seems like it would be good for the machine that is being backed up to locally encrypt, with a symmetric cipher, the data before it is sent off as a block to a peer.

Normally, I would think "use AES". But I'm vaguely aware that there are modes, like CBC. And I'm thinking that chained modes like that would make it very hard to efficiently open a file, seek to a position somewhere near the middle, read a piece of data, encrypt it, and come up with the same cipher text as if it started at the beginning of the file and encrypted all the blocks in order up to that position.

How do the people who do whole disk encryption do this? Is something similar to what they use available for Python (3.x if that matters)?
Why not gpg? The libraries are already written and open sourced, so you don't have to recreate the wheel.

Split the file into blocks, then add a control file adding whatever metadata you need to keep the files together and belonging to the correct person. Encrypt each block with the user's key, and put it on an untrusted host. He will then be the only person who can decrypt the files. Assuming the untrusted host doesn't delete the blocks.