Odd receptacle wiring
This really isn't that odd and yes you can replace them with GFCI's. It is common with multi-wire branch circuits, or in cases where one outlet is switched and another isn't.

In the case of the black and red wire, one is hot and one is neutral. You can identify which one is hot with a multi-meter or non-contact tester (though NC testers can sometimes be misleading).  Do yourself a favor and mark the neutral with white electrical tape wrapped around it once you identify which wire is which.

Don't get too caught up with the wire colours - while you hope people adhere to the standard, there are lots of cases when it's perfectly OK to deviate.