I think there are ~36 possible combinations if you were to consider all of them.
It turns out that there are (a+1) * (b+1) - 1 maximum possible rank combinations for a couples match, where a and b are the number of programs for each couple. In this case, 35. (the reason there are not 36 is because unmatched - unmatched is a pointless "match").
Assuming that living in different cities is unacceptable, your rank list will be shorter than 35.
Couples rank lists are quite interesting. Here are two possible rank lists for you (ignoring the unmatched options, we'll get to those in a second):
List #1
1. 1 - A
2. 2 - B
3. 3 - C
4. 3 - D
5. 3 - E
6. 4 - C
7. 4 - D
8. 4 - E
9. 5 - C
10. 5 - D
11. 5 - E
List #2:
1. 1 - A
2. 2 - B
3. 3 - C
4. 4 - C
5. 5 - C
6. 3 - D
7. 4 - D
8. 5 - D
9. 3 - E
10. 4 - E
11. 5 - E
It would appear that List #1 gives you an advantage, and list #2 gives your partner an advantage. However, neither is true. Assuming that your individual interests are 1>5 and A>E independent of the other person's match, both lists always yield the exact same result!
Try it out -- assume that you are ranked high enough to match at programs 1, 4, and 5; and she is ranked high enough to match at B, C , and E. Both lists will place you at 4 - C. On one list you will get your #4 rank, on the other your #6, but it's the same match either way. You can try it with any combination, and you'll see you get the same match no matter what list you use.
It could be possible that your preferences are not independent, and then some additional ordering would be needed. For example, let's assume that hospital C = hospital 3, hospital D = hospital 4, and hospital E = hospital 5, and you'd prefer to be at the same place. Then your rank list would look like this:
1. 1 - A
2. 2 - B
3. 3 - C
4. 4 - D
5. 5 - E
6. 3 - D (or 4 - C)
7. 3 - E (or 5 - C)
8. 4 - C (or 3 - D)
9. 4 - E (or 5 - D)
10. 5 - C (or 3 - E)
11. 5 - D (or 4 - E)
Note again that ranks 6-11 can be ordered first by either couple -- it won't matter in the final match result. In the example above, this match list would yield a match of 5 - E, stressing being at the same place over individual preferences. However, if we assumed that program 5 did not rank you high enough to match, then this list would again match you at 4 - C (either at rank #8 or at #6 depending on how you rank the final 6-11, but still the same result either way)
What's strange about this is that you assume that matching higher on your rank list is better, and if you're only ranking for a single person it is, but when ranking a couple it's not always true.
I'm going to avoid all the different city matches, but you could list them if you want.
OK, let's deal with the unmatched options. I agree that it makes some sense to favor the person with the tougher match -- presumably the other person will be more successful in the scramble. However that does not always equal the person applying in the less competitive field. Still, there will probably be more spots open in IM than peds. So: (EDIT - the above is incorrect, see post #18)
12. Unmatched - A
13. Unmatched - B
14. Unmatched - C
15. Unmatched - D
16. Unmatched - E
17. 1 - Unmatched
18. 2 - Unmatched
19. 3 - Unmatched
20. 4 - Unmatched
21. 5 - Unmatched
... is probably the best way to go. It might be better to list the NYC programs first, as there are more scramble spots in NYC (in general), although that depends on what areas A / 1 and B / 2 are in.
The other option is this:
12. Unmatched - A
13. 1 - Unmatched
14. Unmatched - B
15. 2 - Unmatched
16. Unmatched - C
17. 3 - Unmatched
18. Unmatched - D
19. 4 - Unmatched
20. Unmatched - E
21. 5 - Unmatched
Note that in this option, it does not matter what order ranks 12 and 13 come in -- you could reverse 12 and 13 and will still end up with the same match (because if both 12 and 13 were possible, you would actually match into rank #1). This gives either of you the top rank possible without the other.