However, the Serial Monitor is spitting out random characters on startup as well as when I try to write normal AT commands.
How do you expect us to explain what appears in the Serial Monitor application, when you failed to show us that?
The Serial Monitor application does NOT randomly spit out characters. It shows ONLY what the Arduino sent.