The way I typically handle this, is there is usually one UI that is the "primary", meaning the UI that you build first. Lets say that the Web UI is the primary. IMO, you need to include some UI in the initial Story otherwise there is no user/customer value to that feature/story.
I will have a Story for each feature, which includes everything necessary to develop and deploy that feature with a Web UI only.
Then I have additional Stories that represent the work to tack on a Phone/Store/Tablet/etc UI onto already developed features. These will be smaller stories, and while I may have split it up into 100 Stories/Features for the WebUI, when scoping the stories for the Phone UI I may group features together, so I may only have 10 Stories for creating Phone UI and each story encompasses an entire area of the application (ie. 1 Phone Story = ~10 Web Stories).