Ballet can also be seen as a form with limited vocabulary. Ballet choreography is certain steps linked together , and many ballets follow similar frames. Execution of the technique is critical for a sucessful ballerina, but the difference between a good ballerina and a great one comes from the execution of those steps. A great dancer can elevate mediocre choreography; brilliant choreographers can bring out the best in their performers.
I think this dual dynamic translates well to the skating world - look at how Michelle Kwan flourished under Lori Nichols' choreography, or how Angela Nikodoniv achieved her highest success while working with Elena Tcherkesskaia (sp). OTOH, Sasha Cohen has a certain sparkle to her skating even when the choreography is so-so (Wagner's R&J), as does Alexander Abt or Emmanuel Sandhu.
Re: pairs and ice dance, the choreography is restricted by the forms - both disciplines hold the two-moving-as-one relationship between the skaters as the highest priority. Pairs has a little more freedom for innovative choreography, but skating separately is still not encouraged (I'm sure there are members who could say what the rules say about it).
Under CoP, there is more of an expectation of choreography, but the past season has shown that most skaters are struggling to add in "choreography" (which generally means adding flourishes to existing elements) while achieving all of the required elements. There is of course room of choreography in the exhibitions, but I imagine that most fans will still want to see the jumps and other tricks, rather than something *completely* different.
One skater who I admire for his willingness to experiment with choreography in his pro career is Ilia Kulik. There is also a dance team who I never noticed in the eligible years but I love their pro programs. Of course I don't know their names....I believe they are Russian or former USSR.