I've never liked using "new" and "first" as my primary stories because they don't last. The new part I've covered before. The first strategy only works as long as there isn't a second, or if you can somehow preserve and own the original idea. Being first demonstrates originality and the willingness to try something new. And that has value...people like that. But, what happens when the second one comes along, and it's better, modified to give people even more of what they want? Then, being first doesn't matter anymore. Here's a list of firsts by Kimpton Hotels (yes, they actually have a list). How important is it (now) that they were the first at any of these things? I suspect that in the case of free internet access, it was pretty important for about a week.
A better approach might be to be "the only". Of course, that's a lot harder...making something that isn't likely to be duplicated, or made better, or cheaper. But, once you do it, you've got marketing built-in, up front, that's going to last...way beyond being first.