I figured it out. I was able to set up a simple call to the GetDBXLVersion method.
After I was able to get the DBXL version call to work, I had my structure figured out correctly, so that meant I could apply it to the other call.At first it didn't work so I started looking into the web service itself.
There are 2 calls to pull from QueryDB, GetColumnsXMLQuery and GetColumnsXMLStrQuery. I was originally using the second, since that's what I use in InfoPath, but the difference is that the second takes the XML query as a string, and the first uses un-escaped XML which is what I was trying to pass.
Now I'm able to return to a simple page ~16,000 records in under 10 seconds.