Need more info to offer you advice. What sort of riding will you be aiming for? Will you be wanting to improve and get to the stage that you can do freestyle and park? Or are you just freeriding, or maybe all mountain with a bit of everything?
Again, need more info to offer advice. Have to know what you're aiming for. Although I do think the 390s are a very solid binding overall. I'd throw the K2 formulas in the ring as well. K2 formulas have to be one of the best all mountain do anything bindings in my opinion.
Don't decide on your boots yet unless you've tried on a ton of different boots at the store. You don't know what will fit best for your feet.
Also, it sounds like you're picking boots that are too big. If your shoe size is a size 9, it's rare that your snowboard boots will be the same size. Snowboard boots are meant to be snug and tight, so you'll typically have boots smaller than your average shoe size. Don't forget that snowboard boots will expand about 1/2 a size to 1 size when you break them in.