Is it bad that I often find myself spending more time on program structure than actually writing code inside methods? Is this common? I feel I spend more time laying the foundation than actually building the house (metaphorically). While I understand that without a good foundation the house will cave in, but does it legitimately need to take half of the project to finalize code structure? I understand design patterns, and I know where to go if I need help on choosing one, but often I find myself doubting my own choices.
No, it's not common, but yes, it should be common.
Having the correct organization of a large project is way more important than any single method in itself. If your project is organized well, it is comparatively easy to understand part of it. If a small change is necessary in one isolated part, it becomes easy to find the class or method concerned, to understand what it does, and to change it from one obvious behaviour to a different obvious behavior.
Having lots of self-contained methods and modules that seem almost to small to make sense is a good thing. Any individual method should be near-trivial to write and read. Many practitioners make the mistake of thinking "Oh, this is trivial to understand, it can't hurt to add a bit more functionality - it will still be pretty clear." Resist that urge with all your power of will; instead, exert this effort on a well-thought-out macro-structure, so that it remains trivial to find, read and change each part when necessary.
(The reasons that this isn't done more often are complex and probably intractable. Writing something that works well at first and slowly becomes unfit for modification seems to give quick return on investment, and many managers are unable to comprehend that a system which you can almost work with may be very expensive to transform into one that you can actually work with in the future. But that's no excuse for not doing the right thing in the first place when experience has taught you to do so.)