Para no tener que pedir un valor al iniciar y creo que esto resuelve el resto de problemas:

    // primero revisar si la coordenada existe
    boolean existe = coordenadas
    .stream()
    .anyMatch(c -> c.getPuntoX() == finalPuntoX && c.getPuntoY() == finalPuntoY);

    // si existe mostrar el mensaje
    if(existe){
        System.out.println("La coordenada ya existe");
    }else{
        System.out.println("Coordenada Agregada a la lista");
        coordenadas.add(nuevaCoordenada); 
    }


El código:

    boolean existe = coordenadas
     .stream()
     .anyMatch(c -> c.getPuntoX() == finalPuntoX && c.getPuntoY() == finalPuntoY);

Puede reemplazarse por:

    boolean existe = false;
    
    for(int i = 0; i < coordenadas.size(); i++){
        if(coordenadas.get(i).getPuntoX() == puntoX 
                 && coordenadas.get(i).getPuntoY() == puntoY)
        {
            existe = true;
            break;
        }
    }

   Código completo

    public static void main (String[] args){
            Scanner entrada = new Scanner(System.in);
    
            CoordenadaCartesiana nuevaCoordenada;
            ArrayList<CoordenadaCartesiana> coordenadas = new ArrayList<>(); //  iniciamos y declaramos el array list que guardara objetos de tipo coordenada
    
            double puntoX; // variable que almacenara punto X
            double puntoY; // variable que almacenara punto Y
            char confirmacion; // confirmacion de ingreso de nueva coordenada
            int menu; // variable que manejara las funciones del menu
    
    
            do{
                do{
                    System.out.println("Ingresa el numero correspondiente a la opcion");
                    System.out.println("1. Agregar Coordenada | 2. Buscar Coordenada | 3. Mostrar Lista | 4. Salir ");
                    menu = entrada.nextInt();
                    if(menu == 1){
                        do{
                            System.out.println("Ingrese el punto X"); // pedir punto X
                            puntoX = entrada.nextDouble(); // guardar dato ingresado
                            System.out.println("Ingrese el punto Y"); // pedir punto Y
                            puntoY = entrada.nextDouble(); // guardar dato ingresado
    
    
                            nuevaCoordenada = new CoordenadaCartesiana(puntoX, puntoY); // los datos seran guardados creando un nuevo objeto coordenada
    
                            double finalPuntoX = puntoX;
                            double finalPuntoY = puntoY;
                            boolean existe = coordenadas.stream().anyMatch(c -> c.getPuntoX() == finalPuntoX && c.getPuntoY() == finalPuntoY);
    
                            if(existe){
                                System.out.println("La coordenada ya existe");
                            }else{
                                System.out.println("Coordenada Agregada a la lista");
                                coordenadas.add(nuevaCoordenada); // dicho objeto es añadido a la lista de coordenadas
                            }
    
    
    
                            System.out.println("¿Quiere ingresar otra coordenada? (s/n)"); // preguntar por siguiente coordenada
                            confirmacion = entrada.next().charAt(0); // guardar respuesta
    
                        }while(confirmacion != 'n'); // si presiona no, el bucle se detendra, creando el objeto con la ultima informacion ingresada
                    }else if(menu == 2){
                        System.out.println("¿Que coordenada desea buscar?");
                        System.out.println("Ingrese el punto X"); // pedir punto X
                        puntoX = entrada.nextDouble(); // guardar dato ingresado
                        System.out.println("Ingrese el punto Y"); // pedir punto Y
                        puntoY = entrada.nextDouble(); // guardar dato ingresado
                        nuevaCoordenada = new CoordenadaCartesiana(puntoX, puntoY);
                        for(int i = 0; i < coordenadas.size(); i++){
                            if(nuevaCoordenada.equals(coordenadas.get(i))){
                                System.out.println("La Coordenada fue encontrada: ");
                                System.out.println(coordenadas.get(i).imprimirCoordenadas(i));
                            }else{
                                System.out.println("La Coordenada no fue encontrada");
                            }
                        }
                    }else if(menu == 3){
                        for(int i = 0; i < coordenadas.size(); i++){ // recorremos la lista
                            System.out.println(coordenadas.get(i).imprimirCoordenadas(i)); // imprimimos el string con la estructura correspondiente ya hecha en el metodo                                                      // pedimos el parametro posicion para poder imprimir el numero al que pertenece en la lista
                        }
                    }
                }while(menu <= 0 || menu > 4);
            }while(menu != 4);
            System.out.println("CERRADO");
        }