I don't think you can create brand by any of the above. Brand is created by users/consumers, brand is a perception. I would imagine that Google would start to see something as "Brand" if there are enough visitors searching for the company name in conjuction with whatever services you are selling. So personally, I do not think the above will help unless it comes together with branded searches for your site.
I would spend that money finding ways to generate customers/clients from places other than google with no thought as to what google thinks of it. Google is going to eat all of our lunches if we keep thinking that they are our friend or partner.
Authority begets brand. Spend the money on becoming the authority.
You need to create a site that makes an impact, so that people will remember it and search for it again. Offer a unique product or service that generates excitement and that nobody else has. It also helps if the site has a type of name that sticks in peoples' minds and is easy to remember. Google will recognize it as a brand when significant numbers of people search for it by its name. For example, if you have a site named "Wally's Widgets", and lots of people remember that name and type it into the search box, then Google will see it as a brand.
"Creating a brand in Google's eyes" is basically the same as "trying to fake a brand for SEO purposes". Spend $20k on a branding agency and get them to develop your brand strategy and do what they say.
The important SEO bits and pieces (link growth for example) will fall into place naturally.
Getting by on SEO alone is all very well when you don't plan to spend any serious cash on developing the website, but if you plan to play with the big boys, then investing in traditional marketing is crucial. It's near impossible to sustain a large business on SEO techniques alone.
Those who do succeed by those means are generally very skilled at content creation, social networking, etc to the point that these techniques could be considered their core products rather than marketing channels.
I disagree. Google will only recognize it as a brand when a lot of people start searching for it by its name.
You don't build a brand for Google
Anyone else think , there might soon be a "bear variant" looking to eat
"built for Google" "Brands"
@aristotle - absolutely agreed - in fact that's probably the key signal used to establish a brand in terms of SEO.
However, looking at the ways you can achieve that, the work of a branding agency and subsequent professional brand strategy is the best route to take. Any work you do to establish a brand offline (or online in a non-SEO capacity) should naturally result in increase brand searches.
Alternatively if you are putting the same hypothetical budget into SEO (or even broader SEM), you may be able to achieve non-branded rankings (or traffic via PPC, etc), but when you've spent your $20k, will there be an established "brand" leftover that will bring you regular business? In some cases yes, but largely no.
The two approaches aren't mutually exclusive however. For example, if you would take what you recommend in your first post - I would consider that as the second step in the process, where the brand strategy is the first.
Creating a site that has an impact is the objective, but the brand strategy is the plan to achieve that. Just going through that process can lead to new ideas that really bolster a SEO campaign. If you can really pinpoint how you want your brand to be perceived, it makes it much easier to identify sites that might want to link to you or to write copy for a PPC ad for example.
All a branding agency would do is give a project some focus and help pad that out into a solid plan of action. It's acutally mostly common sense stuff that most business owners do any way - they just don't think about it in those terms.
Think of it like this - most web developers "do SEO" to a certain extent. They follow basic web standards (which creates a SEO friendly site) for example. They just don't think about it as being SEO.
In the same light, business owners "do brand strategy" to a certain extent.
The turning point in a project is when the developer decides it's time to invest in professional SEO (i.e. the project has grown to a size to justify it). Similarly, a project can grow to the size where professional brand strategy is useful and justified.
The biggest brand builder? Provide the best customer service out there! Folks no longer expect good customer service -- so when you give them above and beyond and blow those low expectations out of the water - that gets them talking to their friends who then in turn will search for you! How about spending some of that 20K on ways to provide unbeatable customer service?
As most people here have already said, the answer is to do what any bricks and mortar company would do if they wanted to become a household name. I doubt that's possible with 15-25k though.