What kind of legal complaint got your hosting yanked? Different places are better for different types of content. If you got a DMCA complaint simply moving offshore (practically anywhere even western Europe) would be enough to keep you out of trouble.
If you are hosting malware/low profile viruses or a high profile site with lots of DMCA type complaints you should move to Eastern Europe, Russia, Ukraine, Turkey, or China (A few places in central America are ok as well Panama/Costa Rica). Straight up botnets/viruses go to Iran/Russia (Iran is likely safer but more expensive).
If you are hosting CP I aint helping you with that and I hope your ass gets busted.
The farther offshore you get the more your going to pay for complaint resistant hosting and the less reliable service you can expect (anyone that sells you bulletproof hosting is full of shit it doesn't exist). Western Europe is a great cheap solution to the occasional DMCA complaint as they aren't under US laws, but have cheap hosting (often cheaper than US hosting).