Sorry for the long post…
My first suggestion would be to try CryptoNight algo (Loki, Haven, TUBE, Ryo, …). It is very friendly with AMD cards, low on electricity and consequently on generated heat. You can use xmr-stak to mine any CryptoNight algo variant. For RX580 8GB you can expect around 1kh/s per card. Regarding rejected shares from NiceHash - be sure to select correct port in URL and corresponding variant of CN algo. I was getting around 5% of rejected shares from NiceHash, but on other pools only a fraction of that number. You can post your flight sheet settings so we can take a look and help troubleshoot. Also, you can try to use custom miner xmrig-amd - it is working, but I have achieved 15% lower hash rate compared to xmr-stak.
Similar to CN, you have the option of Lyra algos (GIN, XVG, …). Also, low on electricity, no need for mem overclocking (you can run mem on 300). Currently, profitability is a bit lower compared to CN, but you can try and see. For RX580 4GB I wasn’t able to achieve expected hash rates on CN algos, so they are for me more profitable running Lyra2z. For that one you can use custom miner tdxminer. I have tried Lyra2REv2 as well using lyclMiner, but profitability is just under what I get with Lyra2z.
As I have mentioned in my previous post, tried running lolMiner as well - it is working but nowhere near the expected profitability, so I think it is currently better to leave that algo to NVIDIAs.
Regarding pools, depends if you are mining coin you believe in (and want to hold on it), or are you looking for current profits… You can choose pools that make payment in the coin you mine, or others that make payments in BTC (NiceHash, MPH, zergpool, zpool, …).
Mining ETH / ETC - oddly enough, difficulty is still very high even though the prices have gone down. Probably, everybody still mining ETH and stuck on it… So, taking into account everything (higher profitability and lower electricity costs) - you can expect up to 30% higher profits compared to mining ETH now.