It is a shame that Internet Radio was removed from ATV4. I wanted to share a solution I've found that works well for me. I am using the StreamStation app (StreamStation on the App Store), which I have installed on all my IOS/ATV devices. It lets you specify any publicly available audio stream by entering the url.
The nicest thing is this app uses iCloud to sync between devices. For me, the easiest thing to do was use iTunes on my Mac to discover streams I like. Then I copied the url text for each stream into the StreamStation app on my iPhone. I also grabbed graphics for these stations from the Web. The app lets you add a graphic for each saved stream. After setting up my favorite streams on iPhone, they are available automatically on StreamStation running on the ATV.
The StreamStation app includes native support for Shoutcast, so you can use that to search for streams. But I found that none of my favorite stations are listed on Shoutcast. Fortunately, you can manually enter url's, and from Internet Radio inside iTunes or other sources I was able to find url's for all the things I like to listen to.