Satellite should be your LAST choice for gaming, especially FPS games, because of the high latencies.
IDSL has very low latency, a speed of 144 kbit/s, and long enough range that almost any residence with copper phone wires can get the service. Unlike ISDN, IDSL is usually sold at a flat monthly rate and is an always-on connection. You can get IDSL service from ISPs such as speakeasy.net -- prepare for sticker shock, however, as it's rather more expensive than Cable or DSL.
3G cellular service, if it's available in your area, can offer surprisingly good speeds (several hundred kbit/s, even exceeding 1 Mbit/s on HSDPA with good coverage), but with worse latency than Cable/DSL (still preferable to satellite, however). Your choices are EVDO (Verizon and Sprint) and HSDPA (Cingular) service; if you don't have coverage for one you might have it for the other. You'll need a PC Card slot; if you have a desktop PC you can probably get an adapter card from your favorite PC parts supplier. Kyocera's KR1 router has a built in card slot, but will only work with EVDO (not HSDPA). You can expect this service to be less expensive than IDSL, but still more (probably at least twice as much) than Cable/DSL.