LinuxCNC vs Mach3 – this topic alone can start a passionate debate, both are capable of controlling 4 or more axes on whatever you choose to attach them to, both have a huge following and support forums. LinuxCNC uses a custom 'real time' kernel to ensure correct synchronisation of all signals on the parallel port, Mach3 uses lots of clever internal software to make the Parallel port behave in a similar manner whilst running under MS Windows, ultimately your choice boils down to how comfortable you are with Linux or MS Windows.
USB vs Parallel port – yes USB is newer, but it doesn't maintain the required timing for multiple step/direction signals at near real time which is required for a CNC machine, various 'off board' processors like Smooth Stepper can be used with Mach3 via a USB port (extra cost), the off board processor handles all of the timing signals. You can't simply use a USB to parallel converter, and many laptops don't have a fully connected parallel port.
Many of the CNC router/engravers available on 'the bay' at around £300.00 – £900.00 could well fit the bill, they claim sizes of 300x400mm up to around 750x450mm.
Prices only really go up from there, depending on how rigid and well specified a router you are willing to pay for, the other option of course is DIY – there are hundreds of different approaches to building a CNC router, many of which have open source or free plans.