Here is what I am generally looking for. Please tell me if you know the best place to get it.

Dedicated Server with:
Red Hat Linux
Plesk (optional but prefered)
256MB Ram (min)
20GB Hard Drive (min)
At least 25 IP addresses (min)
50GB data transfer (min)
other standard features