I have run 500+ MILLION row (uncompressed) table queries on my LAPTOP, taking < 10 seconds each time.

My experience says that indexing is not even close to the main cause of your performance issues here. Talk to me about your server configuration (CPU, RAM and ESPECIALLY IO PERFORMANCE). Note I didn't say "your disks" or "the server's IO". I have a single disk in my my laptop, but I get over 2 GIGABYTES PER SECOND of sequential IO off of it. How much sequential IO can your server do per second, and at what latency?