sync or backup for new iPhone 4?

SMS, notes, photos in the Camera Roll, and contacts are included with your iPhone's backup.

http://support.apple.com/kb/HT1766

Although included with your iPhone's backup, photos in the Camera Roll can and should be imported by your computer as with any other digital camera. After being imported and removed from the Camera Roll after the import process is complete, you can transfer selected photos recently imported from your iPhone's Camera Roll along with any other photos available on your computer from your computer to your iPhone via the iTunes sync process.

http://support.apple.com/kb/HT3603

Although contacts are also included with your iPhone's backup, contacts are designed to be synced with a supported address book application on your computer and should be available on your computer with or without an iPhone or any cell phone which can be lost or stolen.

Notes can also be synced with a supported application on your computer.

SMS/MMS cannot be synced with an application on your computer. The only way to transfer messages from one iPhone to another is by transferring the backup from one iPhone to another which is an all or none proposition. You can't transfer select data only that is included with the iPhone's backup to another iPhone or to an existing iPhone that is restored with iTunes from the iPhone's backup.

-in setting up an iPhone 4, does restoring (instead of syncing) from an Iphone 3 transfer over all slow/laggy issues I had from my iPhone 3? (this is a major concern for me)

Possible, but the iPhone 4 includes a much faster processor than the iPhone 3G and 3GS and double the RAM over the 3GS. If there is a problem with your iPhone's backup, transferring the backup to an existing iPhone when the iPhone is restored with iTunes or to a new iPhone will also restore the problem.

-could I have simply selected "set up as new device" instead? (and retain my SMS, notes, pictures contacts)?

You would not have retained any messages, but if you sync notes with a supported application on your computer, sync contacts with a supported address book application on your computer, and import all photos in the Camera Roll by your computer as with any other digital camera, you can transfer all this data except messages to a new iPhone without transferring the backup for an existing or old iPhone.

http://support.apple.com/kb/HT2109

-would you recommend restoring my iPhone 4 to factory defaults and simply select "set up as new device" THEN sync?

Unless you are having a problem with your iPhone 4, no.

-are there any pitfalls or wear & tear from restoring from an iPhone back-up a thousand and one times (hypothetically)?

No. You will likely purchase a new iPhone long before you restore an existing iPhone with iTunes a thousand and one times or anywhere close to it. It you are having to restore your iPhone with iTunes on a regular basis, something is wrong. The iPhone includes a one year warranty.

-if I instead selected "set up as new device" would itunes OVERwrite the iPhone 3 backup created last night?

No. iTunes creates and maintains a backup for each iDevice which is stored separately.

-what is the generally accepted why to do this transfer?

I didn't care about having access to my messages on my iPhone 3G when I purchased an iPhone 4 so I decided to set up my iPhone 4 as a new iPhone - not transferring the backup for my 3G. This also caused me to lose 3rd party app settings and any data created and stored by a 3rd party app which is also included with the iPhone's backup.