The user story format is pretty flexible.
“As a (type of user), I want (some feature), so that (some goal)”
I've seen this format used successfully at my workplace. For example:
"As a System Administrator, I want copies of the product catalog sent daily to our Sales Partners so that these partners always have the most current version of our product catalog"
In this example:
A feature is defined. The feature might take the name Partner Extract, for instance. It might be implemented as an ETL job that runs nightly to create data files that are made available to Sales Partners via SFTP.
The user story embeds the roles. The two roles identified are System Administrator and Sales Partner.
Incorporating non-functional requirements is easy. The above example includes one non-functional requirement: the product catalog updates must be daily. Requirements that address how much, how fast or how often are non-functional requirements. I like to refer to these requirements as "quality attributes". Here is another example of a user story that expresses a quality attribute:
As a Call Center Representative, I want customer search to return the result in 2 seconds or less (on average) so that customers are not left waiting on the phone.
Write user stories for reliability, security, capacity or any other quality that is deemed important.
Feature Dependencies
You have identified some legitimate limitations of user stories. They are unordered and there is no guarantee they will be independent. In fact, the might be interdependent-- a chicken-and-egg problem. I believe that all non-trivial projects require documentation to supplement the user stories. I watched the agile team here at work create activity diagrams (flow charts) of the business process. These diagrams were used to analyze the feature dependencies. Another approach might be to create PERT diagram in a big all-day session with the customer. In the end, some other artifacts will be necessary to support the user stories.
Epic!
A narrative that describes the scope of a project is a good idea. There should be something like a statement-of-work or a project charter. No serious project should be without one. These documents provide a starting place for identifying user stories. These document help answer tough questions like "What should be the priority of this feature?"
Metadata
After 15 years in the business, I have an opinion about meta-data. In general, it should be avoided. A few reasons include: after a month, no one knows if it is accurate; no one knows if it was updated; it is extra work to create it; you can't predict what metadata will be useful. Most meta-data is a distraction. I like to track owner, author, priority, estimate of effort, and date of last modification. Beyond that, I fight hard to keep meta-data out user stories and use cases.
Benefits (so that...)
I have an opinion about this as well. :-) Including the benefits is vital. Often, users will request a feature without having though about its value. No matter how good an agile team is, the project will fail if it implements unimportant stuff at the expense of more critical functionality. Also as a developer, I do a better job coding a feature if I know how it fits into the big picture. Here is a real-life example of a requirement without justification: "The system shall prevent transactions with EIP and a gift card from occurring.". Huh? What is EIP? Why do I care? Why does anyone care? I don't know. Understanding the context would have been helpful before I went to the business analyst for clarification.
Even worse is when no one remembers why the user story was written. Do we still need this one? Has the business process evolved to the point where this user story is invalid? Does anyone know? These conservations waste time. It gets suckier if the the author of the user story has left the company.
Measurement
Here is an example of user story that is not measurable:
As a Call Center Representative, I want the system to be fast so that customers are not left waiting on the phone.
How fast is fast? A millisecond? A tenth of a second? Ten seconds? Nobody knows. Nobody wants to be wrong so no one every even makes a guess.
Compare that user story to this one:
As a Call Center Representative, I want customer search to return the results in 2 seconds or less (for average daytime call volumes) so that customers are not left waiting on the phone.
This user story is testable. Average day time call volume can be determined from log files. Performance testing can be conducted to determine if the requirement has been met. Even better, the users and developers have agreed on the success criteria well in advance of the end of the project. Testable requirements are a beautiful thing.
I don't know of any long term disadvantages. In the short term, and for a team new to this kind of development, the main disadvantage is that it takes some getting used to and some learning.
The most efficient way to work vertically is to have full-stack developers: in this way a story can be typically executed by one person (or more than one but without pipelining tasks). Clearly this requires that the developers work vertically across the stack (from html to database in the case of a web application).
If your team is not used to working on vertical stories, then they are very likely to be doing the opposite: each person will have knowledge of one layer/tier of the application only. When you introduce vertical stories, you can expect the team to split them into tasks corresponding to layers and then distributing the tasks to different people. This will be very inefficient.
The best approach I can give regarding this is to tolerate this pipelining initially while making it clear that the long term goal is completely different. Have team members across layers pair program so to build up trust and eventually enable people to be completely independent.
I don't agree with the other answer that this approach brings technical debt. It can, but so can any other approach.
Best Answer
They are very generic term actually. There is many way to interpret them, varying in the literature and how people see them. Take everything I say with a huge grain of salt.
Usually, an Epic comprise a very global and not very well defined functionality in your software. It is very broad. It will usually be broken down into smaller user story or feature when you try to make sense of it and making them fit in an agile iteration. Example :
Epic
Feature and User Story are more specific functionality, that you can easily test with acceptance tests. It is often recommended that they be granular enough to fit in a single iteration.
Features usually tend to describe what your software do :
Feature
User stories tend to express what the user want to do :
User story
As bank clerk,
I want to be able to modify the customer information
so that I can keep it up to date.
I don't think there is really a hierarchy between the two, but you can have one if you want or if it fit how you work. A user story can be a specific justification for a feature, or a specific way to do it. Or it can be the other way around. A feature can be a way to realize a user story. Or they can denote the same thing. You can use both : User stories to define what bring business value and feature to describe constraint of the software.
User story: as a customer, I want to pay with the most popular credits cards
Feature support the GOV-TAX-02 XML API of the government.
There is also the question of scenario, which are usually a way a Feature/User story will be executed. They usually map cleanly to a specific acceptance test. For example
Scenario : Withdrawing money
Given I have 2000$ in my bank account
When I withdraw 100$
Then I receive 100$ in cash
And my balance is 1900$
That is how we define those terms where I work. Those definitions are far from a mathematical definition or a standardized term. Its like the difference between a right wing politician or a left wing politician. It depend where you live. In Canada, what is considered right wing may be considered left-wing in the United State. It's very variable.
Seriously, I wouldn't worry too much about it. The important is that everyone on the team agree on a definition so you can understand each other. Some method like scrum tend to define them more formally, but pick what work for you and leave the rest. After all, isn't agile about Individuals and interactions over processes and tools and Working software over comprehensive documentation?