Proper table design for sparse primary key
I'm thinking clustered pk (rule_id, index) 


Do that.  This isn't really a hard case.  (rule_id, index) uniquely identifies a row, so that should be your clustered PK, unless there's some compelling reason to use a different design.  and because


  I will often query the table by rule id only


rule_id should be the leading column in the index.  This supports efficient lookup by rule_id and ensures locality for inserting multiple rows for the same rule_id.