What is the rough "Cost" of a Thread in CPU cycles and memory?

That depends: It depends on the OS, the Java version, and the CPU. The only way to figure this out is to try it and measure the results.

Since you'll be using the ExecutorService, it will be simple to control the number of threads. Don't use too few or requests will stack up. If you use too many, you'll run into performance problems with your file system and the DB long before Java runs out of threads.

Each thread has its own stack, and consequently there's an immediate memory impact. The default thread stack size is ,IIRC, for Java 6, 512k (different JVMs/version will possibly have different defaults). This figure is adjustable using the -Xss option. Consequently using hundreds of threads will have an impact on the memory the VM consumes (quite possibly before any CPU impact unless those threads are running).

I've seen clients run into problems related to threads/memory, since it's not an obvious link. It's trivial to create 100,000 threads (using executors/pools etc.) and memory problems don't appear to be immediately attributable to this.

If you're servicing many clients, you may want to take a look at the Java NIO API and in particular multiplexing, which allows asynchronous network programming. That will permit you to handle many clients with only one thread, and consequently reduce your requirement for a huge number of threads.