First question is - are any of the outlets switched? Also, if any are switched, and technically even if they aren't, its important to be sure that each outlet is controlled by only one circuit breaker.
For the most part you should find the answer to be yes, but its still a really great idea to confirm it, especially since you aren't the person who wired it in the first place. Then you'll have a diagram, and in the event you do end up having any problems, you'll know what outlets and lights and appliances are on what breakers.
So please; do this homework in advance. Your future self will thank you.
Next question, why are you changing them? Do you just want a different color? is there something wrong with them? Also, is any of your wiring aluminum? If so, let us know because there are other things you should be doing.
With that out of the way, looking at the photo you posted, it looks like these outlets are "Screw Clamp" - thats a great thing. But there is another type known as a "quick lock" aka "Backstab" connection which is cheap cheap cheap and quite dangerous. And they look a lot like what you have pictured.
Examples: https://www.handymanhowto.com/electrical-outlets-side-wire-versus-back-wire/
Please read that page, they did a great job of explaining the difference and the danger. The takeaway for you is to NOT USE BACKSTABS for any wiring you do. Do not do it on anything for any reason. Again, your future self will thank you (so will your family and neighbors).
Here is another great read for you, and it addresses the first two questions I asked, mainly being, if you have a switched outlet, or somehow one outlet which is fed by more than one part of a circuit (which is extremely dangerous btw), you need to use breakways for the latter and fix the issue for the former:
https://inspectapedia.com/electric/Electrical_Outlet_Split_Connections.php
Now I'll answer your questions:
- How should I re-wire them?
Exactly the same way they are already. There should be no reason to change how it is wired at all. Unless of course they used backstabs, which, at no point should you use them, and if the outlets you bought have backstabs, then you should use the side screws. You will put all black to HOT (small slot) and all white to NEUTRAL (big slot). ONE wire per screw. Ground goes to chassis.
- Should I also cross them in the replacement receptacle?
When you say "should I cross them?" Well, you should follow my answer to #1, accented by all the material given to read as homework.
If you mean should you have the wires criss-cross around each other in the back, the real answer here, is to just keep the wires untangled, and run them so that when you go to put the outlet back on and screw it down, it will do so without pinching the wires, or causing any sharp bends or folds or kinks. Many times what you see done is the wire is tucked into the back of the box "top to bottom" behind the outlet, and when the box is shallow, or crowded, you'll see it crossed over and tucked into the sides. The point is, dont pinch or cram the outlet back in against the wire. Dont damange the sheathing. And don't trim the wire so that bare copper is hanging out of the outlet past the screw or back-lock hole.
Keep it clean and tidy.
- What is the reason behind cross wiring (if that is the right term to
use)?
Explained in #2.