I would say go with BT for line rental, and Be There for internet. Virgin are fucking shite and they have a bullshit 'traffic management' scheme which means they limit your internet download speed to like 0.00001kb/s (seriously, from my experience, thats not even a joke).
Birmingham has a reputation for being a bit 'rough', but there are plenty of nice areas there too. Where are you travelling from? ![]()