Short Answer: It Depends.
Philosophy is a very broad subject, so what you need to learn depends on what parts of it you wish to focus on. Are you interested in the structure of arguments? Are you interested in specific philosophies, such as ontology, epistemology, phenomenology, etc...? Eastern philosophy? Practical philosophy (philosophy of life)? Philosophy of mind?
If you're interested in the structure of arguments, or in a critical reading of various authors, then you should study logic first.
If you're interested in a specific philosophy, then logic is not necessary, but it can help you decide if a particular view passes the sniff test.
As for who to start with, that too depends, but I think Plato is excellent. It's not so much that Plato's views are or are not tenable, as it is that he anticipated a ton of subjects that are still discussed today. In fact, a common quote is that the history of philosophy is a footnote to Plato. Whether true or not, it gives you an idea of his influence.
Where to go from there depends on your interests. There's a ton of key figures, and even a brief overview would greatly increase the length of this response. One thing that helps if you are reading on a particular topic is to read the key figures in order, as they often build upon or respond to one another. For instance, much of Kant can be read as a response to Hume, Berkeley's views make most sense when seen as a response to "substance theory", and even Existentialism's motto of "Existence Precedes Essence" can be seen as a response to Plato.