I'd run 2x10 outer joists with 2x6 rails inside, flush on the bottom. Suspend them from the 4x4 legs using double concealed-flange hangers set flush to the inside of the posts. This will leave an attractive 1/2" reveal at the outside.
The 2x6 rails will provide a ledge for your deck. Run 3 more 2x6 joists across the gap.
I don't think the diagonals are necessary with this method. The hangers and tall joists will provide substantial diagonal bracing themselves, and your structure isn't that tall. Wind probably isn't much of a concern.