As suggested earlier, this one should be big enough:
RadioShack.com - Cables, Parts & Connectors: Component parts: Breadboards & IC sockets: Multipurpose PC Board with 417 Holes
Anything larger and you can always cut the board down to size (and have leftover board for other projects). I'm fitting my additional circuitry all in the same footprint as the iDuino and stuffing it in the RatShack 4x2x1 box like show in the Workspace thread. The first post in this thread has pictures with the size of board and layout if you want to follow them exactly.
What makes a breadboard (easily) solderable is the copper traces around all the holes on the bottom side. Solder sticks to these and the component. If you get the ones with multiple holes connected, you don't have to worry about trying to bridge the solder from one trace to another, but you're limited in your layout freedom. I recommend getting a larger board than you think is necessary (maybe twice as large), and use a corner to practice your soldering techniques. Then you can build the circuit in the other corner and cut it to size. A small coping saw or band saw work great on these boards.