Yea that sound like a suspect, the PoW that's used to prevent transaction spam. Are you running it inside a VM? Possible 1 CPU core? In your config.json what does it list for work_thread and io_thread count?
The PoW in the transaction makes sense, but I'm not sure why it's needed at address generation time.
By the way - trying to create addresses via the RPC does not appear to be functional. (Something an exchange will likely need)
Got 8 threads - again it's not that long of a time it's down. It's workable. But I imagine an exchange would need to handle at least 100 times more transactions.
What you're noticing is precaching the PoW for your next transaction. I designed the PoW so it uses information from your previous transaction so in the usual case you can fire off 1 transaction instantly and the work generation latency gets hidden in the time until your next transaction.
Part of this will be helped with the OpenCL module I'm putting together for people who need to handle higher transaction loads.