How to design a type safe message API in Java?

I have a Java client which wants to communicate with a device through messages over serial communication. The client should be able to use a clean API, abstracting the ugly details of the serial communication. The client can send many types of messages through that API and gets responses. I'm searching for advice which way is best to implement this API.

For simplicity, say we have only two message types: HelloMessage which triggers a HelloResponse and InitMessage which triggers an InitResponse (in reality, there are many more)

Designing the API (that is, the Java abstraction of the device) I could have:

One method per message type:

public class DeviceAPI {
  public HelloResponse sendHello(HelloMessage){...}
  public InitResponse sendInit(InitMessage){...}
  ... and many more message types ....

This is nicely type safe. (It could also be many times the same send() method, overloaded, but that's about the same). But it is very explicit, and not very flexible - we cannot add messages without modification of the API.

I could also have a single send method, which takes all message types:

class HelloMessage implements Message
class HelloResponse implements Response   
...
public class DeviceAPI {
  public Response send(Message msg){
    if(msg instanceof HelloMessage){
       // do the sending, get the response
       return theHelloResponse
    } else if(msg instanceof ...

This simplifies the API (only one method) and allows for additional Message types to be added later without changing the API. At the same time, it requires the Client to check the Response type and cast it to the right type.

Client code:

DeviceAPI api = new DeviceAPI();
HelloMessage msg = new HelloMessage();
Response rsp = api.send(msg);
if(rsp instanceOf HelloResponse){
    HelloResponse hrsp = (HelloResponse)rsp;
    ... do stuff ...

This is ugly in my opinion.

What do you recommend? Are there other approaches which give cleaner results?

References welcome! How did others solve this?