You were right, you need to create a template. The hardest part is to figure out where to save it so it becomes your default template.
Configure a excel file the way you want, and save it as a template called BOOK.XLT, but not in the default template directory that pops up - instead save to the following location:
C:\Program Files\Microsoft Office\OfficeXX\XLSTART\
(OfficeXX will be dependent on which version of MS Office you have, but you're looking for the one that has a folder called XLSTART in it)
Once you've save it here, close Excel, and next time you open Excel, it should open a new workbook called "Book1" with your new default formatted settings. When you save the new file, it'll give you your default "save as" box as normal. The only difference between this and what you have now is whatever you've added to the default template.
If you ever get tired of how your formatted, just delete the BOOK.XLT file and start over with the new way you'd like it formatted.