Assuming you know how to send emails from your server:

1. Create a stored procedure which sends an email alert when you execute it

2. Create a job, which executes this stored procedure, and when scheduling it, choose an option to start whenever Server Agent starts

So, whenever agent restarts, job will be run, sp will be executed, and alert email will be sent out.

And if whenever your SQL Server restarts, your agent also starts automatically, then you will always get an email whenever either SQL Server restarts or just agent restarts.