Actually, Cyanotype on baryta is an excellent way to not only learn to coat fixed-out paper, but to get really, really nice prints. As you noted, the depth of the blues can be huge. I have never, ever achieved those kinds of tones on cotton paper.
But there are a few things you need to keep in mind when coating on fixed out paper.
1. Always, always double coat...use LOTS of solution, for cyanotype the more the better, just work it in as much as you can and squeegee off the rest.
2. Dont skimp on the tween (or photoflo if it works). Don't worry if it gets all foamy as you scrub it into the paper. The bubbles come off with the squeegee (I use a plastic shower and tub squeegee..don't use a windshield wiper blade, they leave bits behind)
3. Avoid drying the paper between coats with a hot dryer...the paper will start to turn green/grey. Use cool air.
4. Expose promptly. I have found that leaving the paper to rest for even a half hour or so after it is dry allows it to start turning colour.
5. Wash well....you may want to try wash aid. I do for most of my prints.