I have a 4 gal cooler and a 5 gal brew kettle and I've determined that I can mash up to 7.5 lbs of grain fairly comfortably. BeerSmith has been awesome for helping me calculate my recipes. I just enter in an all grain recipe and then drop enough of the base malt to bring the lbs of mashed grains down to about 7 lbs and then add in enough LME to get back to the starting OG. Then I usually fiddle with the amounts to get round measurements. Btw, this setup is big enough to do some low gravity all grain batches, like a cream ale or ordinary bitter. I do have to top up with ~1 gal, but no biggie. Mashing this much grain has made it necessary for me to learn about water chemistry though, and the EZ water calculator spreadsheet has been a huge help with this.
My suggestion would be to buy a 5 gal home depot cooler so you won't need to upgrade right away if you decide to go all grain. With my 4 gal cooler I only loose ~2 degrees over 60 minutes. One thing that really helped me retain heat is to rest 2-3 layers of aluminum foil on top of the mash. Good luck.