Coach seat is a coach seat. They're all cramped. CO's 777 have personal video screens on all seats, while NW's and UA's 744 don't in coach. Legroom are all tight, around 31", unless you can get the "E+" seats on UA (if you have status, or lucky).
CO's flight from EWR departs at 11:10am, so you probably can't get a same-day connection. Earliest MSP-EWR arrives 10:40am, I believe, which is too tight.
Timewise, NW and UA are comparable. About 17 hour outbound, 16 inbound. Since you probably treasure NW miles more than UA, I'll stick with NW, unless UA is significantly cheaper.
The only "premium economy" that you may consider is ANA from New York to Tokyo. But that means 2 connections and flying east to JFK. Not worth the trouble, IMHO.