Paintball bbs aren't a very good idea unless you're going to use them in spring guns.
Uuuurgh! Paintball BB's BAD!
They tend to jam up in the works of semiautomatic airsoft guns (especially gas guns) and then break, filling the internals of your gun with gook. They're alright in single shot spring guns, but most of those don't have the power to throw the paintballs hard enough to break them... You see where the hole in the bucket is, here.
As far as handguns go there are plenty of gas powered airsoft guns that would fit your bill. Anything "gas blowback" is generally a pretty good operational replica, though the quality obviously varies by brand, model, price point, and so forth.
Most airsoft long arms are either spring or electrically powered (by means of an R/C car style battery) and aren't really realistic training aids. There are a few gas blowback rifles, but they are rare and usually fairly expensive.
There are also airsoft 'classics,' which are CO2 powered rifles that were popular in Japan before legislation technically outlawed them; They aren't manufactured anymore but there is still a thriving market for them in places other than Japan (e.g. right here) where CO2 powered playthings are perfectly legal. Classics are powerful, usually quite realistic in heft and operation, but expensive (they don't make them anymore) and tricky to find parts for if they break (again, they don't make them anymore...) so probably not a good choice for a beginner.
However, there are a few companies striving to bring back the concept with updated models in the USA.
Mad Bull Airsoft makes a conversion kit for Tokyo Marui (and their oodles of Taiwanese and Chinese knockoffs) M-16's that replaces the gearbox and provides CO2 blowback operation with real chambering, a moving bolt, &c. They also contracted Systema (I think?) to build the shell of a gun to install the thing in if you don't have an M-16 already, and offer a complete gun to buy with this setup.
Real Action Paintball also make an updated CO2 powered AR-15/M-16 (also an M4, I think) that not only has an accurate working bolt mechanism with blowback but also ejects spent shells. It's spendy, but it's reportedly built like a tank and functions nicely.
The curiously named Youth Engineering (they're China based, I think, and don't seem to have a website) are also rumored to be reviving the old Escort gas system from the Classics days, updating it, and sticking it in an MP5 shell. Nobody's seen any product yet, but it's "coming soon."