When I taught preschool, Kids Yoga was one activity the preschool did with all the age levels to help them tune in to themselves for more body awareness and stress release. By four, some of the kids started participating in team sports, but for many of their parents it was long Saturdays for very little positive impact as they often complained their kids didn't sleep enough, nor did they really get to play on the days their "teams" met up.
Swimming classes don't offer a lot in the way of spatial awareness, but offer good physical activity and teach a valuable life skill (that increases your child's level of safety any time he or she is around water) there are swim classes available in many areas for any age, but for the very young may require a parent to be in the pool with the child. True Body awareness isn't really addressed in these classes until upper levels. I'll admit my own daughter resisted this one, but I at least got her through to a level where I knew she could get herself to a near-by boat, dock or the edge of a swimming pool if she needed to. I grew up on an island so I may value this skill more than many - just wanted to point it out.
In regard to Martial Arts, my daughter started at five and her dojo allows kids to start as early as four but not younger (officially). This article is written by a Judo instructor that seems to agree four is the earliest age for martial arts. Martial arts, like swimming gives kids some great life skills (including along with the physical activity, but won't (until later belts) really help with spatial awareness. In regard to body awareness, Taekwondo (at our studio) desn't really seem to stress body awareness until the second belt. I don't know about other styles.
My daughter was able to do a Gymnastics class with a friend while I was still teaching that was for 3-4 year olds that was great for her and increased her body awareness significantly. While doing gymnastics, she was asked to focus on her body placement quite a bit. I think learning to do a three point stand forced her to become very aware of how she was using every muscle involved in balancing. This article discusses more physical, social and academic benefits specifically for preschoolers who enjoy the sport.
I used to assist with a beginning dance class for 3-5 year olds that also taught rhythm and body awareness quite nicely. We did ballet, tap and contemporary alternating. They have to think about keeping their knees over their toes and all kinds of things that create more awareness because of all the resistance work that gets done. However, with dance you have to be careful because there are a lot of programs out there where kids just wiggle to the music (something that has value too) but won't necessarily increase body awareness.
Your thoughts that gymnastics or karate would both be good options are probably right on, but you might also ask your little one what looks most interesting. Either way you go, there can be quite an expense involved in proper attire and paying for classes. You'll want to know your little one is interested, not totally freaked out and game before you sign the dotted line.