This is one of those things that has changed through the years. Think about Dr Samuel Johnson’s Twitter-feed for example – it’s partly effective because of its use of capitals. But nowadays, it’s “less is more”.
Of course, we always use a capital letter at the beginning of a sentence, and traditionally we use one after a colon, too (although this is no longer set in stone – the rule is: be consistent).
Proper names are still capitalized, so: Liz, the city of London (when referring to the place as a whole) but the City of London when referring to that specific region of the city.
Some words are capitalized (or not) to distinguish between an abstract and a concrete use of the term. For example, the Methodist Church as an organisation, but a Methodist church as a building. In a similar way, State is capitalized when you’re talking about a particular state – New York State, or the State of New York as an entity, but when talking about the states of New York and Wisconsin, no capital. And when you’re referring to something you’ve mentioned before, such as the University of Birmingham, you call it “the university” thereafter. The same with people: Prince William, but “the prince said”, etc.
Although this isn’t strictly a “troublesome pair”, the rest of them are here.