Everyone tells me to make sure the camera feels good as far as layout and size.
This is very important. I use my 10D a lot, and often my hands feel rather "raw" after extended use with heavy lenses. While the 10D fits me OK, the 1 series would be an even better fit. Thus, the camera should feel right in your hands. The only universal complaint I have regarding the 350D is that there is no job dial at the back. Having to press a button to change aperture is just a pain. However, if you never had a DSLR before, I doubt you will care much about this one.
Not to sound sexist, but most girls do have smaller hands and thus prefer the smaller camera bodies. If you find the 350D fits you better and you are satisfied with the layout, then go for it.
As this is my First SLR would the 20D have more features than my limited knowledge will use?
Hmm this one is subjective. If you love photography and is determined to learn, then there isn't such thing as having more feature that you never learn to use. While the 20D provides some features that the 350D doesn't, those features aren't THAT significant, i.e. mirror lock-up, which is a great feature to have if you are shooting high magnification, most 350D users don't even shoot macro!
What makes the 20D more rugged than the Rebel XT?
While I can not quote you manufacturing tolerance data and stress testing results, I have seen 300D's fall apart from too much use, then again I have also seen 20D's die from too much use. I use my 10D in the rain, and it isn't even weather sealed
Since this is your first DSLR, why not go for the 350D, and spend the price difference on a good tripod and decent lenses? Ok I might be exaggerating, the price difference isn't enough to buy all that, but you get my point. Tripods are the cheapest way to get consistant results, it's a surprise how many people spend an arm and a leg on their camera and lenses only to whimp out on the tripod. Also, it would be a good idea to add some budget quota for a few books. I recommand the books by John Shaw, just look on Amazon.