What you see in windowed mode is usually more or less the original resolution of the game. If you scale it to fullscreen, this little picture is just stretched, thus the pixels look much bigger. What you can try is using a different scaling mode, which smooths the edges. The whole picture will look softer and maybe a bit blurred then. Some people like this better others prefer the crisp pixelated look of the original. After all it's an old game and this pixel look and feel provides some of the old charm. No matter which scaling filter you're using, you'll never get a high-resolution game, comparable to nowadays standards.

To change the scaling engine, run the "Graphic Mode Setup" (it's in the game's folder).
- Set Graphic Mode to OpenGL
- Under Advanced Settings you can try different Scaling Engines (default is normal2x)

Here are examples how the different engines look like:
http://www.dosbox.com/wiki/Scaler

Thanks for the reply. I went through every setting with "Graphic Mode Setup" and still couldn't get it to look good. Oh well I will just have to play as is. This is not a problem, I just want to replay them.

I'm afraid it won't get any better on a big display. You could also play it in windowed mode and set the windowed resolution in the Advanced Settings tab to strike a balance between windowed in original resolution and fullscreen.