You're safest with crossover cables for both. However, some network ports do auto-sense the type of cable, and correct for it automatically - if you could find the specs for your network interfaces, it should state whether or not they are auto sensing. But, it's easiest and safest to just get crossover cables - they will definitely work.
If the PCs are close together, I think you could get away with CAT5 - no need for CAT6.
Also, note that CAT5 & CAT6 are grades of cable - they have nothing to do with whether the cable is crossover or straight-through.
Another thing - it is less likely that the 10/100 port will auto-sense the type of cable - the ability to auto-sense the cable type is more common with Gigabit ports.
If you did want to connect all the PCs together at some stage, a Gigabit switch will work with the 10/100 port. The other ports will still work at full (gigabit) speed, so the use of the switch would not degrade performance at all. If you were to get a switch, you would then buy straight-through cables, *not* crossover cables.
So a crossover cable will work at gigabit speeds for the gigabit to gigabit connection? To get the fastest connection between the two gigabit connections - do I specifically need to get a crossover cable that's specifically rated for gigabit or it doesn't matter?
Get a crossover cable, yes. The crossover cable is required for it to work at all. You would still need a crossover cable for it to work at all even if you were running at a speed significantly less than gigabit. Just ignore my comments about autosensing, and get a crossover cable.
The aspect of the cable which matters for "gigabit speed" is the grade of cable. The grade of cable is defined by the "CAT" number.
My understanding is that for gigabit, you are supposed to use CAT6. (or CAT5e) But in my opinion (and I have done a bit of Googling to check), you can probably get away with CAT5, if the two computers you are connecting are close together. (like, a few feet apart, or even, say, 10 or 20 feet apart). If you can afford the CAT6, just get CAT6 to remove all possible risk. Having said this, I notice that my local electronics store *only* stocks CAT6 now. So, it appears that CAT6 is the norm. If your store stocks both types, it's unlikely that there will be much difference in price.
In simple summary: buy two CAT6 crossover cables. ;^)