Other vegetables that go well with salmon (or other fish for that matter) include asparagus, broccoli, green beans, zucchini, etc. If you want a fresh vegetable salad, a creamy cucumber salad with dill is a great choice.