+1 on the CBC. I don't think we will see the real BBC as many BBC shows have exclucive deals for US broadcast. BBC World News would be nice, though. Al Jazzera English might make a nice contrast to US sources. Retro Television Network would be nice as Cleveland has no affiliate.
Now new HD, that is a topic for aother thread. But since some are talking about it anyway, Comedy Central, E! and Spike would make me happy (although the first 2 don't exist yet).