If you go with a blenny make sure you dont get a scooter blenny. Basically same as a mandarin for feeding. I love Lawnmower Blenny's and with a nice tank size like yours, one would probably do well if the system is matured.
There is no reason you cant plan to have the mandarin evetually by adding a fuge with chaeto and letting it establish. The reason I bring this up is because if you do plan for it, you dont want other fish that eat pods
such as a six line wrasse. It will make it even harder for the mandarin to get food.