House Smallwood reminds me of another question. I noticed a couple of the men up on the Wall are from noble houses, but not knights. Are these fellows who commited crimes or otherwise disgraced themselves before knighthood? Or, in the case of the Smallwoods at least, are they followers of the old gods like the Blackwoods?

The Smallwoods don't follow the old gods, no. But many houses have junior branches, cousins of the lordly lineage who branched off generations back. They have the name, but not the wealth, nor the castle... and they won't necessarily be knights.