Mazera and Warfare Incorporated are both sold now by Astraware.

Mazera: http://www.astraware.com/palm/mazera/
Warfare Incorporated: http://www.astraware.com/palm/action/warfare/

There's demos for each there. In fact Astraware does have a lot of good Palm games. Some of the other good ones I've tried (but not on my n800 yet):

Tradewinds: http://www.astraware.com/palm/strategy/tradewinds/
Tradewinds 2: http://www.astraware.com/palm/strategy/tradewinds2/
Westward: http://www.astraware.com/palm/strategy/westward/
Zap 2000/2016: http://www.astraware.com/palm/action/zap2000/
Zuma: http://www.astraware.com/palm/action/zuma/

Again, haven't tried these ones on my n800 yet, they're just great Palm games. Unfortunately none are free, but they do all have demos.

As for screenshots, here's a couple from each.

The last one was too big to upload here, so here's an imageshack link: