I'm wanting to start a newsletter on my site but would like it so that I submit the article to my news module and then it send out an e-mail notification to everyone with the newsletter.

So is there a way where I can set it so that all users have a notification by default when they register?

And is it possible I could run into issues with a user base of over 25,000 users with my server?

These are two separated things.
The notifications are open to everyone to subscribe on, so they get an email (or PM) message when a new story is added. Different options are available, so the user can subcribe only to the categories of interest.
A Newsletter is typically a summary of all articles publicized in a period (month, week). It is composed or generated by the admin and then sent to the subscribers.
When you want to notify on each article to the newsletter subscribers, depending on the article publicizing rate, you risk to annoy them and make them unsubscribe.

If you want to mix both systems, you need some tighter coupling by changing the notification event of News, using the users from the newsletter subscription.

When sending mail to thousands of users, you risk the problems that come with mass mailing: servers that block mails to 100+ addresses; other instances may catalogue you as a SPAM site; ...