If Bitcoin addresses are truely random, then why are some more difficult to generate than others? In this post TierNolan explains why 'Bitpoin' is much easier to generate than 'bitpoin', and that mainly has to do with the position (first character). But I remember that certain characters (I believe 'i' and 'o') are much more difficult to generate, independant of their position in the address. How is this possible?
The 160-bit hash that is encoded in addresses is uniformly distributed ("truely random" as you call it), but the base58 encoded form is not. Some characters are more likely to occur at the start, for example.

To illustrate, consided the set of all integers between 0 and 1999. Even though each of those numbers is equally likely to be chosen, this is not true for its decimal representation. There, half of the numbers start with a 1!