Who will store the seed that used for Google auth?

If u use truly random password then u r ok. Recent horror stories r just black PR tricks.

You are probably right - but you can't be sure.   And this difference between "probably right probably safe" and "sure certain" is the shadow of doubt that the public mind will seize upon that will hinder widespread adaptation of NXT.  Bitcoin will always be able to claim an air gap option that we will not.  Getting ahead of this with some form of account freeze blockchain option two step authentication scheme is the right thing to do.

The problem with using an authenticator, in their current forms, is that they rely on a centralized point -- google, a SMS gateway, whatever.  

That, and it'd need multisig implemented.

Except the multisig, this is something that a NXT service provider could solve, I think.  I imagine it would work like this:

A group of nodes would run a parallel blockchain for the NXT2SMS functions.  These nodes would use transparent forging between themselves to maintain their N2S blockchain.  When you need to send a SMS, you would pay a fee and have a payload as an arbitrary message on the main blockchain.  The N2S nodes would notice the payload and decide who on their blockchain gets to collect the fee and transmit whatever is represented in the payload over SMS.  The one who generates the SMS is also the one who does the other side of the multisig to release the funds.

There's lots of hand-waving in the above paragraph because I don't know exactly how the core NXT functions that this is build upon will operate as they're yet to be released, but it's the general idea.

The hardware for the SMS transmission is the simple part as that already exists as an off-the-shelf solution: a smartphone or, for the more hardware hacker oriented, a GSM/GPRS module and an Arduio/RPi/etc to interface to it.

I might have overlooked something, however.

Not only that. Íf there is some bad mediacoverage, we can point out that these issues have been debated amongst the stakeholders before launch and prove that we take security seriously and are also thinking beyond the scope of advanced users. I'm trying to think long term about these things as much as possible.

It has been always been 256 bits.

Quick question on the theft issue:

If someone is just running a brute force attack on the whole NXT network attempting to hit the jackpot, wont this activity be very visible in the blockchain?
Way I see it, every password generated by the brute force attack will create an account.
Can anyone (with more skillz than me) have a look at the account creation (possibly vs IP address) stats and see if something wierd is showing up?

The account will not show up in the blockchain before a transaction is made.

Brute force attack is completely offline.