What is the best way to store sensitive information on the client? I am very inexperienced with cryptography and would like some advice on how to store some sensitive information on client machines.

I have some information stored in a central database on my server. A snapshot of this database is distributed along with my application. Every time the application is opened on the client, it checks for any new information on the server and downloads it via a web service. We need the information to be protected at all times, even when stored on the client. The only time it should be decrypted is while it is in memory and being used by the application.

I realize that the nature of our application means that no matter how strong our encryption scheme is, someone could still access our data by examining their machine's memory after the data has been decrypted. However, we have decided that we are OK with that scenario unless there is some magical way of dealing with this problem that I don't know about. We don't need absolute security for this data. We basically just need to raise the difficulty enough to deter most people from tinkering with it.

It seems to me that using a symmetric key is probably the best approach for this scenario. My concern is that if someone figures out the key, we'll have no way of knowing it. Even if we did manage to find out, it would be extremely difficult for us to change it since we would have so many clients using the old key. The natural way of solving this problem is to periodically change the key, but then how do we securely deliver the new key to our existing clients?

It is also worth noting that the user of the application doesn't know about this data and doesn't care about it. We can't ask for a password, require them to have a network connection, or impose any other limitations on them.

Looking forward to your thoughts on this. :)
What you want is basically impossible in this way. The crux of the matter is that if you want your application to access the encrypted data, your application needs to have the key in some shape or form. 

Due to the limitations you mentioned, this key needs to be on the client machine, in the application's code or data files.

There are several ways to hide a key in the application's data.  But that is really "security through obscurity", e.g. no security at all. Because it won't protect the key against a persistent attacker who could e.g. single-step through your application's assembly code in a debugger to see how it is accessing the database.

To keep out casual snoopers, you could just compress the database before writing it to disk. To make snooper's lives more difficult, you could chop off the identifying header that most compression programs employ.

BTW, the existence of virtual machines makes snooping on an application easier and harder to detect than ever before. There are some tricks to detect wether your program is running under a debugger, in which case you could abort the program. But if that machine is virtual, the attacker could stop the VM at any time and trawl through that VM's memory at his leisure without your program being any the wiser.

Another thing to keep in mind is authentication. How does the client authenticate to the server when it wants to retrieve a database update? In other words, what is stopping an attacker from impersonating your application and requesting a complete copy of the database?