I've kept a pincushion urchin and a red fromia starfish in my IM Nuvo 40 and they had no issues with each other.
If I had to recommend one over the other it would definitely be the urchin. While they can be bulldozers at times, they are basically a reef tank roomba when it comes to consuming algae, and you can find some pretty colorful varieties.
Starfish are great visual additions, but fromias don't eat algae and sandstars can wipe out your sandbed microfauna. Fromias typically don't last long in captivity either, as we don't know exactly what they eat so it's hard to supplement their diet. Mine lasted about a year before he started disintegrating, which is typically how they go.