Cicero has become synonymous was difficult Latin, but I think that this is unfounded and is based more on the faulty teaching methods of schools than his style. As Gonzalo says (and the book "Cicero's Style" by Michael von Albrecht), Cicero's lexicon is quite small as he was interested in maintaining an understandable and 'pure' style. The benefit is that before you know it you'll have picked up most of the vocabulary and be reading quickly, which in turn will allow you to focus on grammar and absorb new words in context.
To second Gonzalo, Cicero's philosophical writings are easier and less ornate than his various orations. The content can be more abstract, but Cicero was a down-to-earth guy and it shows in how he discusses philosophy. It's not difficult at all to understand. As you guessed, reading the orations can be a pain if you're lacking the historical background (I've found this out the hard way). The Catiline orations aren't bad, as you can follow what's going on from the context (Catiline=bad; Cicero=good). The benefit of the philosophical works is that they're generally self-contained and rely on reasoning rather than reference.
I enjoyed the De Amicitia and recommend it, and the subject of friendship is inviting. De Senectute, "Old Age," is good too depending on your interests. De Officiis, "Duties," is easy to read in my opinion, but it's also quite systematic and boring. De Amicitia and De Senectute (like the Tusculanae Disuptationes) are in dialogue form and so are more lively and interesting. You'll be in a better position to approach the orations once you've become comfortable in his prose.Homo Ciceronianus
, which Gonzalo and I write together, has been in hibernation recently because of my sloth, but look forward to a revival when I finish my last term paper tomorrow and can begin to think about something other than English literature again. Perhaps I'll pen an article on Thomas Hardy