Without an Active Directory Domain to apply Group Policy from creating policy settings on the Terminal Server computer that apply only to "normal users" but not to "Administrators" is going to be a hack. (You'll have to deny "Administrators" rights to read the "%SystemRoot%\System32\GroupPolicy" folder-- the location where "local group policy" is stored.)
You can probably accomplish what you're looking for by using a different shell (the "Custom user interface" policy, located in the "System" node under "Administrative Templates" under "User Configuration"), but what shell you decide to use is going to be your next problem. There were a proliferation of replacements for "Program Manager", the Windows 3.1 shell, but after Explorer came along in Windows 95 the alternative shell "market" dried up significantly. Do some digging and see what you can come up with.
Personally, I have some disagreement with what you're trying to do. Unless this is a kiosk environment it's probably not really necessary to highly constrain the user interface. My guess is that your users will get their work done and things will go fine w/o requiring massive changes and "locking down" the user interface on the Terminal Server computer. Assuming your users don't have "Administrator" privileges on the Terminal Server computer and you haven't made any sweeping changes to the default security settings (file system, registry ACLs, etc) then the machine is fairly well "armored" against user attack "out of the box".