Yeah, it does sound complex, as opposed to just a bunch of lines separating states, etc. Hard to make the paths.
The postscript problem is being generated by Publisher and there's little you can do about it. That's always been the underlying problem with that app.
Since the underlying components are tiffs, you're already rasterized at 400 dpi. If the map has to be blown up to meet the final size of 28x40 you will lose quality. If not you have several options.
I'd guess the best would be to open Distiller, part of Acrobat, and go to Settings - that's where you get Press/print/screen, etc. Create a setting with NO downsampling. Call it something like 0. Take out all the text used in Publisher if possible. Then create the pdf using your 0 setting. You should be able to select that setting via Writer.
Then use Photoshop to open that pdf. If you get a screen asking for resolution select Leave As Is or 600 (minimum-1200 better) dpi. Don't pay any attention to the screen size - only the print size. Create a new, transparent layer (so you can undo later if necessary) in Photoshop and add the text. You can then save as one giant tiff and send to the printer. You're best off saving a copy of the Photoshop file, flattening that and mke that the tiff. The reason I mentioned the high resolution is that text need far higher resolution than the underlying tiffs for final print. That pdf Press setting sets text resolution at 2400.
Another possibility is to go through the steps up to opening in Photoshop and use the Place command in Illustrator to set the pdf. Then add the text in Illustrator and use the pdf export command. Again, select the 0 setting you made. You could also send the printer the Illustrator file but, if you do so, make sure to include copies of all the fonts used.
Using OSX 10.3.9 on a G4