I would suggest a dungeon map whose layout is semi-modular so that it can be customized by application of a few tiles atop it, or alternately several variously shaped rooms with labeled exits Instead of connecting hallways. In my experience, 300ppi is best for printing.

Also, if you are going to get it laminated (a very wise decision) you could do a generic floor tile pattern and add walls with an erasable marker.