I'll add my weight to the Bronze Age Minis argument. I recently bought 12 of their barbarians (so basically most of them!) and they are fabulous sculpts! The newer ones are a bit larger than the older models in the range, but that doesn't really matter unless you really have a thing about figure sizes.
Reaper do some fabulous barbarians too, although you need to search a bit in order to find the best ones - there are some super Tre Manor sculpts in amongst them, but he's by no means the only sculptor in there with decent work.
If you want Picts, one novel idea would be Bob Murch's pre-gunpowder Iroquois Indians in his Huron/Iroquois war/Flint and Feather range. The Picts in the Conan stories always strike me as more Eastern Woodland Indian than Neanderthal and the raiders who appear early in the most recent Conan movie are basically exactly that - savage looking Woodland Indian types...
Good luck!
