Personally I would use irfanview ... it's free and easy to use.
http://www.irfanview.com/
I am not familiar with the Nikon software (sorry).
Don't worry about the KB size as much as the X by Y resolution. You don't want to lower the JPEG compression as much as reduce the XY data being sent to the printer. This is because the printer does not take JPEGs it actually takes bitmaps so you are only losing clarity when you lower the compression.
Here are the steps I would use:
1) Get and install IrfanView
2) Use it to load one of your old pictures (from the CD)
3) Look in the bottom left of the window for the size of the picture (some thing like 640x480x24BPP) write it down or memorize it. The numbers that are important are the first number (Width) and the Second Number (Height)
4) Fill up all the pictures you want to do into a single directory.(from the Nikon)
5) Under the file menu select Batch Conversion
6) Set up a convienient Output Directory
7) Go to the Picture Directory and Add All
8) Near the bottom Click on Batch Conversion and Check on the Use Advanced Options.
9) Click on Set advanced options
10) Under advanced check the RESIZE box and fill in the Width and Height with the numbers you found in 3.
11) Check Preserve aspect ratio (proportional)
12) Optional step (Save Settings)
13) Click OK
14) (You are now back on the Batch Conversion screen) Click Start.
You should now have a whole bunch of resized pictures in your directory. Use your standard printing program to make them 4 up ...
Good luck ...