I would talk the guy with the Yugo down - a "new" rifle is one that hasn't been fired, especially through 100's of rounds.
Also, the side-rail optics mount is very helpful. Definitely consider this.
Finally, have you considered a simple, Romanian WASR? For under $400 they are a great deal and some are surprisingly nice if you can inspect it before hand. They are not as nice as either of the rifles you are considering but much cheaper and they will come with side-optics-mount, sling, mags, bayonet, etc, etc.