Yes, Red is the first PMD to come out for the Advance. The Blue version came out for DS. No, you don't need link cable to rescue someone from either games. Just SOS wonder mail code, believe that you enter to go help.
The follow up to the pair is Time/Darkness/Sky.