It is a common theme. Your scenario #1 is a storage optimization over scenario #2. In #2, you have to generate and store a random value server side. This gives you all the control you may want, but requires an extra column in your database, or something like that. Scenario offloads this storage requirement client-side. Since the client cannot be trusted, you have to add to the link an integrity check, i.e. a MAC; encryption is not needed because there is nothing in the reset link that you need to keep secret from the user (the user already knows his name and when he asked for a password reset), but you want to prevent a malicious client from creating a fake reset link, hence the MAC.
The token contents, in scenario #1, must therefore include all the data that you need to enforce your password reset policy, but chose not to store on the server; this means the user name and a time stamp (time at which the password reset process was triggered, or expiry time). You might want to include a hash of the previous password in the input to the MAC (not necessarily in the token) if you want to prevent the user from reusing the reset link several times.
Computing and verifying a MAC won't take a lot of resources, probably a tad less than generating a random token and storing it in a database (the database access will be considerably more expensive than the cryptography). However, chances are that this effect is negligible anyway (databases are fast). A disadvantage of scenario #1 is that you need to keep a secret key on the server, shared between the front-ends (if you have several), resilient to reboots (so not a key in RAM only, unless you are ready to invalidate all password reset links when the server reboots), and, of course, safe from eavesdroppers.
The random token (scenario #2) is probably easier, or, if you prefer, harder to get wrong. Which is a good enough reason to recommend it.