another problem is that I need GENE to always be first (not regular lexicographic sort)

That's doable...here's a sample (the sed and awk can easily be replaced by perl...left as an exercise):

#!/bin/ksh

awk 'BEGIN {
  SORTCD["GENE"] = 1
  SORTCD["CDS"]  = 2
  SORTCD["RNA"]  = 3
}
{ print SORTCD[$3], $0 }' <<EOT |
1 1 RNA
1 1 GENE
1 2 CDS
EOT
sort -n -k2,3 -k1,1 | sed -e 's/^[0-9]* //'
[download]