What is the main difference between user stories and functional specifications (other than the format they are in)? When should I use user stories and when specifications. Do they go hand in hand with agile and waterfall respectively?
Functional specification is typically a quite detailed document which describes the system, it can take weeks and months to create it. Classically it is used in Waterfall, but in my practice I had clients who came to us with this 100-page doc and asked to develop using Agile. So the functional specification is broken down into small tasks and iterations are planned out of these tasks.
User stories and mainly used in Agile and give the possibility to start development very quickly. You don't have to know and describe all the future product functionality, only that for the first sprint.
What is the main difference between user stories and functional specifications (other than the format they are in)?
A story is a promise to have a conversation about requirements. Specifications are the record of this conversation. (Based on JimStandley comment here.)