Unsized paper is fine.
15-30 minute exposures seem rather long, but its hard to judge without
knowing the intensity of your light source. Have you tried direct
sunlight?
I think you are going to want to get a print frame of some kind so that
you get good contact between your negative and the coated paper.
I think you are right about your negative. Cyanotypes negatives should
ideally have a long tonal range and a contrast such that you would
need to use grade 1 or 0 gel-silver paper to get a good print.
Coated cyanotype paper does not store very well at all. It goes bad
overnight. Mix the sensitizer and coat just before use.
Hope this helps,
Bob Schramm