For encoding work at that budget, you'll want to prioritize CPU cores over RAM. Look at Contabo's VPS range — they offer decent multi-core plans around €10-15/mo with enough power for video encoding. Hetzner Cloud is another option with good price/performance ratio.
For the upload/download part, make sure the provider doesn't throttle bandwidth. Some cheap VPS providers cap you at 100Mbps or have hidden fair-use policies that kick in after a few TB.
Another approach: use a dedicated server from Hetzner auction — you can sometimes get older hardware with great specs for under €30/mo. Way more power than any VPS at that price point.